大意是在一条直线上,有N个从0..N-1编号的城市,每个城市之间的道路有最大负载ai,现在有M张从i城到j城的运货订单,假设每个城市的货物无限,问在某一时刻,如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？
首先,这是一个区间调度问题,性质如同问:有许多项工作,每个工作有起始结束时间,目标是尽可能多的选择工作,问最多可参与几项工作? 工作结束得越早,那么之后可选择的工作自然越多. 这道题是一样的,货物的终点站越靠左,那么留出了越多道路给后面的订单. 这里是贪心的思想.
再然后就是对于这些按终点排好序的订单进行贪心选择过程中,维护一段区间容量最小值. 每完成一张单,要把该区间的容量减去这段区间的容量最小值,相当于这段路被这张单"充斥了这么多"..
比如A--5--B--2--C. 对于ABC这三座城市,决定要完成A到C的订单,那么应该变成A--3--B--0--C.这里用线段树来维护. 这篇文章其实也主要是想说说这个线段树有哪些要注意的地方.
日常遇到的最朴素的线段树比如要维护a b c d,有4个值,维护的区间是[1, 4], 那么这个区间划分子区间的时候是[1,2]和[3,4]即可,但是这里的城市有点不同, 城市与城市之间,是共用端点的. 所以假设是4个城市a b c d,编号 1 2 3 4, 那么整体的区间是[1,4] , mid = (1 + 4) / 2 = 2, 子区间是[1, 2]和[2,4] 其中[2,4]应该再子区间成[2,3][3,4]才对.
于是! 对于这种端点的意义应当重叠的线段树区间,定义子区间的端点应该有以下变化:
由
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
变成
#define lson l, m, rt << 1
#define rson m, r, rt << 1 | 1
另外,还有个小坑点.就是平时上面我说的第一种情况,端点不重合的时候,对于update和query函数,我喜欢,一般这样也足矣
// [L, R]是查询的区间, l, r, rt对应当前节点的区间信息
if (L <= r && r <= R)
return seg[rt];
但是对于这种区间重合的题,比如我要查询城市[u,v]的情况, 假设我到了[1,u]区间,此时,我们不论查询什么,返回的都是错的,因为这个区间和[u,v]没有任何关系(返回个错值也就算了,因为进入了错误区间,永远达不到正确区间而无限递归才是它真正的宿命..真是个寂寞的结果阿...喝茶). 而上述的第一种情况中,我们不会进入这种毫不相干的区间..(除非你在进入子区间的时候if条件多留意判断一下)
总而言之,端点重合的时候,要么加上条件不符合时跳出判断,要么在进入的时候多留意关系.
代码从一般情况下的:
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R)
return seg[rt];
...
int m = (l + r) >> 1;
if (L <= m) // 去访问左区间;
if (R > m) // 去访问右区间;
...
变化成
ll query(ll L, ll R, ll l, ll r, ll rt) {
// 跳出无效区间
if (R <= l || L >= r) return inf;
if (L <= l && r <= R)
return seg[rt];
ll m = (l + r) >> 1;
ll ret = 直接访问左区间 访问右区间 之后的结果(反正走错了子区间兜着(会跳出来))
return ret;
}
或者是
ll query(ll L, ll R, ll l, ll r, ll rt) {
if (L <= l && r <= R)
return seg[rt];
ll m = (l + r) >> 1;
// 当端点完全被L覆盖,即<而非<=再前往这个区间= (=对于这种城市是无效的)
if (L < m) ret = 去访问左区间;
if (R > m) ret = 去访问右区间;
return ret;
}
说这么多..其实线段树的想法很清晰,但是细节对于每一题都不尽相同..细节也是比较需要经验和加深记忆的地方...最终代码如下
/* 有人说这题用int能过.其实不能 signed maxInt=2^31-1.题目最大值是2^31*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define lson l, m, rt << 1
#define rson m, r, rt << 1 | 1
#define ct pair<ll,ll>
const ll inf = 0x3f3f3f3f3f3f3f3f, maxN = 100005;
ll N, M;
ll seg[maxN << 2], lz[maxN << 2];
ct edge[maxN];
void push_up(ll rt) { seg[rt] = min(seg[rt << 1], seg[rt << 1 | 1]); }
void push_down(ll rt) {
if (!lz[rt])
return;
lz[rt << 1] += lz[rt];
lz[rt << 1 | 1] += lz[rt];
seg[rt << 1] += lz[rt];
seg[rt << 1 | 1] += lz[rt];
lz[rt] = 0;
}
void build(ll l, ll r, ll rt) {
lz[rt] = 0;
if (l + 1 == r) {
scanf("%lld", &seg[rt]);
return;
}
ll m = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
ll query(ll L, ll R, ll l, ll r, ll rt) {
// 跳出无效圈
if (R <= l || L >= r) return inf;
if (L <= l && r <= R)
return seg[rt];
push_down(rt);
ll m = (l + r) >> 1;
ll ret = min(query(L, R, lson), query(L, R, rson));
return ret;
}
void update(ll L, ll R, ll x, ll l, ll r, ll rt) {
if (R <= l || L >= r)
return;
if (L <= l && r <= R) {
lz[rt] += x;
seg[rt] += x;
return;
}
push_down(rt);
ll m = (l + r) >> 1;
if (L <= m)
update(L, R, x, lson);
if (R > m)
update(L, R, x, rson);
push_up(rt);
}
bool cmp(const ct& A, const ct& B) { return A.se < B.se; }
int main() {
// freopen("data.in", "r", stdin);
scanf("%lld %lld", &N, &M);
build(1, N, 1);
rep(i, 0, M) {
scanf("%lld %lld", &edge[i].fi, &edge[i].se);
++edge[i].fi, ++edge[i].se;
if (edge[i].fi > edge[i].se)
swap(edge[i].fi, edge[i].se);
}
sort(edge, edge + M, cmp);
ll ans = 0;
rep(i, 0, M) {
ll a = edge[i].fi, b = edge[i].se;
ll can_get = query(a, b, 1, N, 1);
ans += can_get;
update(a, b, -can_get, 1, N, 1);
}
printf("%lld", ans);
return 0;
}
