P7619 [COCI 2011/2012 #2] RASPORED
题目描述
Mirko 的比萨店是城里最好的,镇上所有的居民每天午餐都吃比萨饼。而且 Mirko 的送货服务很快,送货时间可以忽略不计。但是 Mirko 只有一个小烤箱,一次只能烤一个比萨饼。
我们将城里的 $N$ 个居民从 $1$ 到 $N$ 编号,他们计划吃午餐的时间为 $L_i$,Mirko 需要为他们烘焙比萨的所需时间为 $T_i$。
如果一个居民在他计划吃午餐时间的前 $K$ 个时间单位收到了他的比萨饼,那么 Mirko 会得到 $K$ 元小费。相应地,如果一个居民在他计划吃午餐时间的后 $K$ 个时间单位才收到了他的比萨饼,那么 Mirko 必须向居民付款 $K$ 元。如果比萨饼准时送到,Mirko 不会得到小费,但是也不用付任何费用。
请你帮助 Mirko 安排一天的比萨烘焙顺序,使得他一天赚取的**总小费最大**。
**注意:**
1. 一天从时间单位 $0$ 开始,你可以认为这一天是无限长的。
2. 居民们有时会改变他们的 $T_i,L_i$。
输入格式
无
输出格式
无
说明/提示
#### 【样例 1 解释】
最优的比萨烘焙顺序为 $(1,3,2)$。这样的话,第 $1$ 个比萨在第 $2$ 个时间单位送达,第 $3$ 个比萨在第 $5$ 个时间单位送达,第 $2$ 个比萨在第 $10$ 个时间单位送达。
第 $1$ 个比萨由于早送了 $8$ 个时间单位,所以 Mirko 得到了 $8$ 元小费;第 $2$ 个比萨由于迟送了 $1$ 个时间单位,所以 Mirko 需要付 $1$ 元;第 $3$ 个比萨由于迟送了 $4$ 个时间单位,所以 Mirko 需要付 $1$ 元。因此最大的总小费为 $3$。
经过第 $1$ 次修改后,比萨烘焙顺序没有变,小费变成了 $5,0,-3$。
经过第 $2$ 次修改后,比萨烘焙顺序变为 $(1,2,3)$,小费变成了 $5,0,-11$。
#### 【数据范围】
对于 $50\%$ 的数据,$1 \le T_i,T_j \le 10^3$。
对于 $100\%$ 的数据,$1 \le N,C \le 2 \times 10^5$,$0 \le L_i,L_j \le 10^5$,$1 \le T_i,T_j \le 10^5$,$1 \le R_j \le N$。
#### 【说明】
本题分值按 COCI 原题设置,满分 $150$。
题目译自 **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #2](https://hsin.hr/coci/archive/2011_2012/contest2_tasks.pdf)** ___T6 RASPORED___。