自动搬运

查看原文

来自洛谷，原作者为

	风中の菜鸡 。

搬运于2025-08-24 21:30:27，当前版本为作者最后更新于2021-10-18 20:27:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了几篇题解，感觉分析的不是很清楚，所以我就来一篇详细分析的题解，像我这样的蒟蒻都能看懂（巨佬请自行跳过）。

注意题目中的一句话："当一个人向上走，另一人向下走而在楼道里相遇时，向上走的人将手中的箱子交给另一人，两人同时反向。即原来拿箱子向上走的人不拿箱子向下走，原来不拿箱子向下走的人现拿着箱子向上走。"其实这句话根本不需要考虑，因为所有人速度一样，所以谁接手谁的箱子去送是一样的，因此我们就不需要考虑了。

然后这道题就变成了一道数学题了，不难发现一个人从起始位置出发，再以同样的状态回到此位置的时间是固定的，这个时间就是 $2(n-1)$ 。至于为什么，请看下图。

看到这有人可能以为再次以同样状态回到出发楼层的时间不应该是 $2n$ 吗，但请你仔细想想，你从一楼爬到五楼要爬几层？正解应该是四层，因为你不是从 $0$ 楼出发。

得到这个结论后，做出此题就不难了。

我们的思路：

$1$ . 输入时预处理每个人到顶楼的距离。

$2$ . 从小到大对这个距离排序。（至于干嘛下面解释）

$3$ . 算出搬完这些箱子需要几个来回。

$4$ . 用来回数乘上一个来回所用时间。

$5$ . 在加上最慢的返回第 $n$ 楼所用时间。（因为第 $4$ 步操作仅仅算出了回到起始位置所用时间，但其实还要搬到顶楼才搬完）

这道题就做完了，上代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k,m,ans,minn=1e9,t[500010];
int a[500010];
int main(){
//	freopen("box.in","r",stdin);
//	freopen("box.out","w",stdout);
	cin>>n>>k>>m;
	for(int i=1;i<=k;i++){
		int b;
		cin>>a[i]>>b;
		if(b==1){
			t[i]=a[i]-n;
		}
		else{
			t[i]=n-a[i];
		}//预处理出每个人到顶楼时间。 
	}
	sort(t+1,t+k+1);
	t[0]=t[k]; //m%k==0时情况 
	cout<<2*(n-1)*(m/k)+t[m%k];//公式 
	return 0;//完结撒花
}