P1798 小明搬家题解
风中の菜鸡
·
·
题解
看了几篇题解，感觉分析的不是很清楚，所以我就来一篇详细分析的题解，像我这样的蒟蒻都能看懂（巨佬请自行跳过）。
注意题目中的一句话："当一个人向上走，另一人向下走而在楼道里相遇时，向上走的人将手中的箱子交给另一人，两人同时反向。即原来拿箱子向上走的人不拿箱子向下走，原来不拿箱子向下走的人现拿着箱子向上走。"其实这句话根本不需要考虑，因为所有人速度一样，所以谁接手谁的箱子去送是一样的，因此我们就不需要考虑了。
然后这道题就变成了一道数学题了，不难发现一个人从起始位置出发，再以同样的状态回到此位置的时间是固定的，这个时间就是 2(n-1) 。至于为什么，请看下图。
看到这有人可能以为再次以同样状态回到出发楼层的时间不应该是 2n 吗，但请你仔细想想，你从一楼爬到五楼要爬几层？正解应该是四层，因为你不是从 0 楼出发。
得到这个结论后，做出此题就不难了。
我们的思路：
$2$ . 从小到大对这个距离排序。（至于干嘛下面解释）
$3$ . 算出搬完这些箱子需要几个来回。
$4$ . 用来回数乘上一个来回所用时间。
$5$ . 在加上最慢的返回第 $n$ 楼所用时间。（因为第 $4$ 步操作仅仅算出了回到起始位置所用时间，但其实还要搬到顶楼才搬完）
这道题就做完了，上代码：
```cpp
#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;//完结撒花
}
```