L3-017 森森快递 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N−1)编号。由于道路限制,第i号城市(i=0,⋯,N−2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci​公斤。

公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj​号城市运输到Tj​号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。

为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。

输入格式:

输入在第一行给出两个正整数NQ(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公斤。

分析:每个路程受到其中最小承重量限制,不同的运输路线[a, b],[c,d]之间有3种关系 1.[a, b]与[c,d]无交集,则可以同时进行两个运输订单 2.如果一个路线包含于另一个路线中,那么选择少的那一段显然更优 3.[a, b]与[c,d]存在交集,交集为[c,b],则能最大运输货物重量为min([c,b],[a,c] + [b,d]。 综上,我们可以将点坐标,按照右端点从小到大的顺序排列,相等的情况下,按照左端点从小到大的顺序排列。只需要建立一棵具有区间加以及区间最小值的线段树即可,符合结分配合律,故不需要lazy数组。遍历排序后的接线信息,每个路线取到最大运输货物后,减少本线路的通货承重量,即可得到最终答案~

注意:输入的路线起始与结束不一定小的在前面,大的在后面~

 

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版