比赛场次 | 230 |
---|---|
比赛名称 | 20140414 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2014-04-14 08:00:00 |
结束时间 | 2014-04-14 11:30:00 |
开放分组 | 全部用户 |
注释介绍 | usaco 2014 2月月赛金组题 |
题目名称 | 登机 |
---|---|
输入输出 | boarding.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
zgyzhaoguangyang | AWAWWWWWWW | 0.479 s | 9.32 MiB | 20 |
HZOI_lhy111 | AWWWWWWWWW | 0.245 s | 0.31 MiB | 10 |
zjmfrank2012 | AWWWWWWWWW | 0.388 s | 1.29 MiB | 10 |
LuciFer_T-J | AWWWWWWWWW | 0.439 s | 1.66 MiB | 10 |
◆半城烟沙灬為你打天下 | AWWWWWWWWW | 0.519 s | 2.60 MiB | 10 |
隨風巽 | AWWWWWWWWW | 0.574 s | 7.94 MiB | 10 |
Suke | AWWWWWWWWW | 0.845 s | 3.37 MiB | 10 |
ys | AWWWWWWWWW | 1.526 s | 4.40 MiB | 10 |
digital-T | AWWTTTTTTT | 7.032 s | 1.07 MiB | 10 |
Miku_lyt | AWTTTTTTTT | 8.165 s | 2.49 MiB | 10 |
cstdio | AWTTTTTTTT | 8.288 s | 3.36 MiB | 10 |
GDFRWMY | C | 0.000 s | 0.00 MiB | 0 |
hzoi_zyl | C | 0.000 s | 0.00 MiB | 0 |
FF_Sky||幻 | WWWWWWWWWW | 0.285 s | 2.59 MiB | 0 |
OI永别 | WWWTTTTTTT | 7.036 s | 4.13 MiB | 0 |
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达到自己想要的座位:
-2 | -1 | 0 | 1 | 2 | 3 | |
牛 | 1 | 2 | ||||
座椅 | 1 | 2 | 3 |
这一共花了1 + 5 + 3 + 10 = 19秒。
在此键入。