比赛场次 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 简单对比
用户 结果 时间 内存 得分
Gravatarzgyzhaoguangyang AWAWWWWWWW 0.479 s 9.32 MiB 20
GravatarHZOI_lhy111 AWWWWWWWWW 0.245 s 0.31 MiB 10
Gravatarzjmfrank2012 AWWWWWWWWW 0.388 s 1.29 MiB 10
GravatarLuciFer_T-J AWWWWWWWWW 0.439 s 1.66 MiB 10
Gravatar◆半城烟沙灬為你打天下 AWWWWWWWWW 0.519 s 2.60 MiB 10
Gravatar隨風巽 AWWWWWWWWW 0.574 s 7.94 MiB 10
GravatarSuke AWWWWWWWWW 0.845 s 3.37 MiB 10
Gravatarys AWWWWWWWWW 1.526 s 4.40 MiB 10
Gravatardigital-T AWWTTTTTTT 7.032 s 1.07 MiB 10
GravatarMiku_lyt AWTTTTTTTT 8.165 s 2.49 MiB 10
Gravatarcstdio AWTTTTTTTT 8.288 s 3.36 MiB 10
GravatarGDFRWMY C 0.000 s 0.00 MiB 0
Gravatarhzoi_zyl C 0.000 s 0.00 MiB 0
GravatarFF_Sky||幻 WWWWWWWWWW 0.285 s 2.59 MiB 0
GravatarOI永别 WWWTTTTTTT 7.036 s 4.13 MiB 0

登机

★   输入文件:boarding.in   输出文件:boarding.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


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

需要5秒的奶牛1坐下来,10秒奶牛2坐下来,总共需要10秒

这一共花了1 + 5 + 3 + 10 = 19秒。

 


【来源】

在此键入。