问题6929--牛吃草大会 II

6929: 牛吃草大会 II

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述



【题目描述】

虽然在接机上耽误了挺长时间,Farmer John为吃草爱好牛们举行的大会至今为止都非常顺利。大会吸引了世界各地的奶牛。

然而大会的重头戏看起来却给Farmer John带来了一些新的安排上的困扰。他的农场上的一块非常小的牧草地出产一种据某些识货的奶牛说是世界上最美味的品种的草。因此,所有参会的N头奶牛(1≤N≤10^5)都想要品尝一下这种草。由于这块牧草地小到仅能容纳一头奶牛,这很有可能会导致排起长龙。

Farmer John知道每头奶牛i计划到达这块特殊的牧草地的时间ai,以及当轮到她时,她计划品尝这种草花费的时间ti。当奶牛i开始吃草时,她会在离开前花费全部ti的时间,此时其他到达的奶牛需要排队等候。如果这块牧草地空出来的时候多头奶牛同时在等候,那么资历最深的奶牛将会是下一头品尝鲜草的奶牛。需要说明的是,恰好在另一头奶牛吃完草离开时到达的奶牛被认为是在等待的。类似地,如果当没有奶牛在吃草的时候有多头奶牛同时到达,那么资历最深的奶牛是下一头吃草的奶牛。

请帮助FJ计算所有奶牛中在队伍里等待的时间(ai到这头奶牛开始吃草之间的时间)的最大值。

输入格式convention2.in):

输入的第一行包含N。以下N行按资历顺序给出了N头奶牛的信息(资历最深的奶牛排在最前面)。每行包含一头奶牛的aiti。所有的ti为不超过10^4的正整数,所有的ai为不超过10^9的正整数。

输出格式】convention2.out):

输出所有奶牛中的最长等待时间。

输入样例

5

25 3

105 30

20 50

10 17

100 10

输出样例

10

【样例说明】

在这个例子中,我们有5头奶牛(按输入中的顺序编号为1..5)。奶牛4最先到达(时间10),在她吃完之前(时间27)奶牛1和奶牛3都到达了。由于奶牛1拥有较深的资历,所以她先吃,从她到达开始共计等待了2个单位时间。她在时间30结束吃草,随后奶牛3开始吃草,从她到达开始共计等待了10单位时间。在一段没有奶牛吃草的时间过后,奶牛5到达,在她正在吃草的时间里奶牛2也到达了,在5个单位时间之后能够吃到草。相比于到达时间等待最久的奶牛是奶牛3

 

来源/分类