网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO FEB14]登机
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | boarding.in | 输出文件 | boarding.out |
【题目描述】
FJ的牛已经决定去度假,并奇迹般地找到一个航空公司愿意出售他们的票。然而,当他们到达机场开始登机,面临的是一个有趣的问题 。
飞机有N个座位,我们叫位置x = 1到x = N,在一个数轴上。所有的奶牛 (1 <= N <= 200,000)正在排队在等待进入他们的座位。刚开始,奶牛N是在位置x = 0,奶牛N-1是在位置x = -1,等等。牛i被分配到牛座s_i,这里s_1,……,s_n是排列1,……,N.
在每一个时间步,每头奶牛需要走一步找到正确的座位如果她能。当奶牛i一到她的座位s_i,她将停下来,把她的行李放在上面的行李架上,用时t_i秒,然后坐下来。对于那些t_i秒时间,在她后面(如果有)的牛会被阻止向前。如果有一队牛在她身后,都将被阻止向前。
所有的牛坐好需要多久?
所有奶牛的t_i将少于1000000000。
【输入格式】
第1行为N;
接下来有N行(2--N+1),两个整数s_i和t_i;
【输出格式】
输出只有一行,即需要的时间。
【样例输入】
3 2 5 3 10 1 5
【样例输出】
19
【提示】
输入输出解释:
最初,牛是位于这样:
牛 -> 123
123<- 座椅
-2 | -1 | 0 | 1 | 2 | 3 | |
牛 | 1 | 2 | 3 | |||
座椅 | 1 | 2 | 3 |
牛1试图去坐2,2只想坐3,和牛3要座1。 一步后,他们都会向前走1步,牛3将达到她的座位1.
-2 | -1 | 0 | 1 | 2 | 3 | |
牛 | 1 | 2 | 3 | |||
座椅 | 1 | 2 | 3 |
牛3用时5秒放行李,然后坐到座位上.
-2 | -1 | 0 | 1 | 2 | 3 | |
牛 | 1 | 2 | ||||
座椅 | 1 | 2 | 3 |
3秒后奶牛1和奶牛2达到自己想要的座位:
-
需要5秒的奶牛1坐下来,10秒奶牛2坐下来,总共需要10秒
-2 | -1 | 0 | 1 | 2 | 3 | |
牛 | 1 | 2 | ||||
座椅 | 1 | 2 | 3 |
这一共花了1 + 5 + 3 + 10 = 19秒。
【来源】
在此键入。