简答题
偏难
#7555
森森快递 森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N-1)编号。由于…
森森快递
森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N-1)编号。由于道路限制,第i号城市(i=0, … , N-2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。
为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。
时间限制:5000
内存限制:262144
输入
输入在第一行给出两个正整数N和Q(2 ≤ N ≤ 105, 1 ≤ Q ≤ 105),表示总共的城市数以及订单数量。 第二行给出(N-1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci(i=0, … , N-2)。题目保证每个Ci是不超过231的非负整数。 接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。
输出
在一行中输出可运输货物的最大重量。
样例输入
10 6 0 7 8 5 2 3 1 9 10 0 9 1 8 2 7 6 3 4 5 4 2
样例输出
7
提示
样例提示: 我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f3f
using namespace std;
typedef pair<int,int> pa;
typedef long long ll;
int n,q;
ll ans;
int v[100005];
pa p[100005];
int tree[400005],lazy[400005];
bool cmp(const pa &a,const pa &b) {
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
void build(int l,int r,int t) {
lazy[t] = 0;
if(l == r) tree[t] = v[l];
else {
int mid = (l + r) >> 1;
build(l,mid,t << 1);
build(mid + 1,r,t << 1 | 1);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
void pushdown(int t) {
if(lazy[t] == 0) return;
lazy[t << 1] += lazy[t];
lazy[t << 1 | 1] += lazy[t];
tree[t << 1] -= lazy[t];
tree[t << 1 | 1] -= lazy[t];
lazy[t] = 0;
}
void update(int l,int r,int t,int L,int R,int d) {
if(l >= L && r <= R) tree[t] -= d,lazy[t] += d;
else {
pushdown(t);
int mid = (l + r) >> 1;
if(mid >= L) update(l,mid,t << 1,L,R,d);
if(mid < R) update(mid + 1,r,t << 1 | 1,L,R,d);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
ll query(int l,int r,int t,int L,int R) {
if(l >= L && r <= R) return tree[t];
if(l > R || r < L) return inf;
int mid = (l + r) >> 1;
ll d = inf;
pushdown(t);
if(mid >= L) d = min(d,query(l,mid,t << 1,L,R));
if(mid < R) d = min(d,query(mid + 1,r,t << 1 | 1,L,R));
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
return d;
}
int main() {
scanf("%d%d",&n,&q);
for(int i = 0;i < n - 1;i ++) {
scanf("%d",&v[i]);
}
build(0,n - 2,1);
for(int i = 0;i < q;i ++) {
scanf("%d%d",&p[i].first,&p[i].second);
if(p[i].first > p[i].second) swap(p[i].first,p[i].second);
p[i].second --;
}
sort(p,p + q,cmp);
for(int i = 0;i < q;i ++) {
ll d = query(0,n - 2,1,p[i].first,p[i].second);
ans += d;
update(0,n - 2,1,p[i].first,p[i].second,d);
}
printf("%lld",ans);
}</pre>
这道题暂未补解析。