当前位置:首页 > 二分 > 正文
洛谷P1798小明搬家[NOI导刊]
152+

题目大意:m个箱子在起点,要运到距离为L的终点,n个搬运工正在搬运,需要多少时间才能搬完?

题目描述

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

小明现在住在第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层的人一定正不拿箱子向下走。

输出格式

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

输入输出样例

输入样例 #1

5 2 4
1 0
3 0

输出样例 #1

20

说明

对于30%的数据有K≤100,M≤100;

对于60%的数据有K≤1000,M≤l09;

对于100%的数据有K≤500000,M≤109。

解题思路

时间越长,搬得越多,具有单调性,我们很容易想到二分答案。

对于时间m,能搬运多少箱子?逐个人计算累计答案即可。如果手上没箱子,先花s-1+a[i]-1的时间搬一个,剩下时间向下取整搬箱子即可,这样可以避免出现负数影响答案;如果手上有箱子,先花s-a[i]的时间搬一个,如果搬不了则无解。

当然,也有很多其他解法,如先统一方向,然后以n个人搬1个箱子为周期计算,剩下不足n个再逐个搬或者直接算剩下k个箱子的耗时。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P1798小明搬家[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter