[NOIP2010冲刺五]小明搬家

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 box.in 输出文件 box.out

【题目描述】

小明要搬家了,大家都来帮忙。

小明现在住在第N楼,总共K个人要把X个大箱子搬上N楼。

最开始X个箱子都在1楼,但是经过一段混乱的搬运已经乱掉了。最后大家发现这样混乱地搬运过程效率太低了,于是总结出了提高效率的方法。

大家的速度都是每分钟上(或下)一层楼。所有向上走的人手中都拿一个箱子,所有向下走的人手中都不拿箱子。到达第N层立刻放下箱子向下走,到达第1层立刻拿起箱子向上走。当一个人向上走,另一人向下走而在楼道里相遇时,向上走的人将手中的箱子交给另一人,两人同时反向。即原来拿箱子向上走的人不拿箱子向下走,原来不拿箱子向下走的人现拿着箱子向上走。

求将所有箱子搬完所需的最短时间。

【输入格式】

第一行N(N10^9)K(K500000)M(M10^9),分别表示楼层数、人数、还放在一楼地上的箱子数。

接下来K行,每行两个数AiBi

Ai表示第i人现所在的楼层数,Bi01,为0表示第i人正拿着箱子向上走,为1表示第i人不拿箱子向下走。

输入满足没有任意两人正在同一楼层,在第1层的人一定正拿着箱子向上走,在第N层的人一定正不拿箱子向下走。

【输出格式】

仅包含一个整数,为搬完箱子的时间。

【样例输入】

5 2 4
1 0
3 0

【样例输出】

20

【提示】

对于30%的数据有K100M100

对于60%的数据有K1000Ml09;

对于l000/o的数据有K500000M109


【来源】

冲刺NOIP2010模拟试题与解析(五)(提高组复赛)