首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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 &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;algorithm&gt;   #define inf 0x3f3f3f3f3f using namespace std; typedef pair&lt;int,int&gt; 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 &amp;a,const pa &amp;b) {     if(a.second == b.second) return a.first &lt; b.first;     return a.second &lt; 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) &gt;&gt; 1;         build(l,mid,t &lt;&lt; 1);         build(mid + 1,r,t &lt;&lt; 1 | 1);         tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     } } void pushdown(int t) {     if(lazy[t] == 0) return;     lazy[t &lt;&lt; 1] += lazy[t];     lazy[t &lt;&lt; 1 | 1] += lazy[t];     tree[t &lt;&lt; 1] -= lazy[t];     tree[t &lt;&lt; 1 | 1] -= lazy[t];     lazy[t] = 0; } void update(int l,int r,int t,int L,int R,int d) {     if(l &gt;= L &amp;&amp; r &lt;= R) tree[t] -= d,lazy[t] += d;     else {         pushdown(t);         int mid = (l + r) &gt;&gt; 1;         if(mid &gt;= L) update(l,mid,t &lt;&lt; 1,L,R,d);         if(mid &lt; R) update(mid + 1,r,t &lt;&lt; 1 | 1,L,R,d);         tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     } } ll query(int l,int r,int t,int L,int R) {     if(l &gt;= L &amp;&amp; r &lt;= R) return tree[t];     if(l &gt; R || r &lt; L) return inf;     int mid = (l + r) &gt;&gt; 1;     ll d = inf;     pushdown(t);     if(mid &gt;= L) d = min(d,query(l,mid,t &lt;&lt; 1,L,R));     if(mid &lt; R) d = min(d,query(mid + 1,r,t &lt;&lt; 1 | 1,L,R));     tree[t] = min(tree[t &lt;&lt; 1],tree[t &lt;&lt; 1 | 1]);     return d; } int main() {     scanf("%d%d",&amp;n,&amp;q);     for(int i = 0;i &lt; n - 1;i ++) {         scanf("%d",&amp;v[i]);     }     build(0,n - 2,1);     for(int i = 0;i &lt; q;i ++) {         scanf("%d%d",&amp;p[i].first,&amp;p[i].second);         if(p[i].first &gt; p[i].second) swap(p[i].first,p[i].second);         p[i].second --;     }     sort(p,p + q,cmp);     for(int i = 0;i &lt; 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>
这道题暂未补解析。