网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NOIP2010冲刺五]小明搬家
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | box.in | 输出文件 | box.out |
【题目描述】
小明要搬家了,大家都来帮忙。
小明现在住在第N楼,总共K个人要把X个大箱子搬上N楼。
最开始X个箱子都在1楼,但是经过一段混乱的搬运已经乱掉了。最后大家发现这样混乱地搬运过程效率太低了,于是总结出了提高效率的方法。
大家的速度都是每分钟上(或下)一层楼。所有向上走的人手中都拿一个箱子,所有向下走的人手中都不拿箱子。到达第N层立刻放下箱子向下走,到达第1层立刻拿起箱子向上走。当一个人向上走,另一人向下走而在楼道里相遇时,向上走的人将手中的箱子交给另一人,两人同时反向。即原来拿箱子向上走的人不拿箱子向下走,原来不拿箱子向下走的人现拿着箱子向上走。
求将所有箱子搬完所需的最短时间。
【输入格式】
第一行N(N≤10^9),K(K≤500000),M(M≤10^9),分别表示楼层数、人数、还放在一楼地上的箱子数。
接下来K行,每行两个数Ai,Bi。
Ai表示第i人现所在的楼层数,Bi为0或1,为0表示第i人正拿着箱子向上走,为1表示第i人不拿箱子向下走。
输入满足没有任意两人正在同一楼层,在第1层的人一定正拿着箱子向上走,在第N层的人一定正不拿箱子向下走。
【输出格式】
仅包含一个整数,为搬完箱子的时间。
【样例输入】
5 2 4 1 0 3 0
【样例输出】
20
【提示】
对于30%的数据有K≤100,M≤100;
对于60%的数据有K≤1000,M≤l09;
对于l000/o的数据有K≤500000,M≤109。
【来源】
冲刺NOIP2010模拟试题与解析(五)(提高组复赛)