问题 24774 --【USACO2014FebGold】boarding

24774: 【USACO2014FebGold】boarding

时间限制: 5 Sec  内存限制: 256 MB
提交: 1  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

Problem 3: boarding

【题目描述】

    想象一下火车有N个座位,N个座位相当于数轴上的1至N共N个整点,第1个座位在整点1处,第2个座位在整点2处,。。。第N个座位在整点N处。

N个奶牛排好队,要登陆坐火车,第N头奶牛在数轴的整点0处,第N-1头奶牛在数轴的整点-1处,。。。。第1头奶牛在数轴的整点-N+1处。第i头奶牛的座位号是Si。注意:每头奶牛都有唯一的一个座位,不会出现多头奶牛有相同的座位号。

    在每一秒钟,奶牛会向右移动一步到达下一个整点,前提是没有奶牛挡住它。

当第i头奶牛到达它的座位Si时,它需要花费Ti秒去把行李放到头顶的行李架上,然后坐到自己的位置上,在次过程中,由于火车通道很窄,所以在第i头奶牛坐到自己座位之前,在它左边的所有奶牛都不能动,要等奶牛i放好行李坐好后才能动。    

    现在的问题是,至少要多少秒之后,所有的奶牛都能做到自己的座位上?

【输入格式】

     第一行,一个整数N1 <= N <= 200000

     接下来有N行,第i行有两个整数SiTi,表示第i头奶牛的参数。所有Ti之和不超过10^9  

【输出格式】

     一个整数。

【输入样例】

     3

     2 5

     3 10

     1 5

【输出样例】

     19

【样例解释】

1 + 5 + 3 + 10 = 19

提示


Analysis: Airplane Boarding by Steven Hao





We will compute the number of steps each cow takes before sitting down, starting with cow N and going down sequentially.



We will store a set of pairs of two integers. Each pair represents a seat and a time: a pair (3, 4) means that a cow wishing to move to seat infinity must pass by seat 3 at time 4.



For cow N, the set contains only (0, 0); the only restriction we have on cow N is that he must be at position 0 at time 0. For cow N - i, the set will contain at least (-i, 0) as cow N - i must be at position -i at time 0.



We can find the first time cow i can reach seat S[i] by searching the set for the pair (a, b) such that a < S[i] and b - a is maximized. If cow i is restricted by the pair (a, b), then cow i will reach seat S[i] at time b - a + S[i] and will sit down at time b - a + S[i] + T[i].



To maintain the set when transitioning from one cow to the next, we simply look at all the pairs the most recently inserted cow passed by and subtract 1 from the position. In other words: if cow i is in seat 5 at time 10, then cow i - 1 can not be past seat 4 at time 10.



This immediately yields a O(N^2) solution. We will store the set as an array of pairs.



For cow i, search for the pair (a, b) with the maximum value of b - a satisfying a < S[i]. Compute the time cow i sits down (V[i] = b - a + S[i] + T[i]). Then, insert the pair (S[i], V[i]) into the list (cow i must be at seat S[i] at time V[i]). To transition to cow i - 1, we perform a range update by replacing all (a, b) such that a <= S[i] with (a - 1, b). We then print out the maximum value of V taken over all cows.



The O(N log N) solution stores the set as a monotonic queue. We observe that we do not need to store two pairs (a, b) and (c, d) if a < c and b - a > d - c; the pair (c, d) will never be the maximum of any prefix. Furthermore, in any subset, the pair (a, b) with the maximum value of b - a is simply the pair with maximum a.



To maintain the monotonic queue, after inserting a pair (a, b), delete all pairs (c, d) with c >= a and d - c <= b - a. Note that the range update does not a

来源

 

[提交][状态]