自动搬运

查看原文

来自洛谷，原作者为

	Ghosty_Neutrino ♬ Just do it！♬

搬运于2025-08-24 23:17:03，当前版本为作者最后更新于2025-05-31 01:57:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定沿直线排列的 $N$ 户人家，每户人家在时刻 $T_i$ 将退货物品摆出，对应位置为 $X_i$。卡车需从位置 $0$ 出发，按位置递增顺序访问所有人家并回收物品，最后返回位置 $0$。求完成任务的最短时间。

分析

卡车经过住户位置的时刻必须 $\ge$ 其摆货时间 $T_i$，否则需等到 $T_i$ 时刻才能回收物品。

我们可以发现，由于住户沿直线排列，卡车的最优访问路径必然是先到达某一端点，再按顺序访问另一端。原因如下：

• 要保证时间最短途中一定不能折返，确定方向后一直走到底再折回来。
• 只需考虑两种顺序：第一种是卡车从 $0$ 开始从左往右依次访问所有住户最后返回 $0$，第二种是卡车从 $0$ 开始先直接开到最右边的住户位置再从右往左依次访问所有住户，直到回到 $0$ 结束。

我们可以把住户的位置从小到大排序方便左右访问。

把两种情况都算出来再比较谁更小就是答案。

但是，这题不用先从左到右的那种情况，因为两种情况都要加上卡车不访问任何住户的情况下走完 $0$ 到最右端住户的位置的距离，而且在卡车先开到最右端时会先消耗时间，回来时等待住户拿出物品的时间就会变少。于是，代码就变成了以下这样。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=3010;
int n;
struct D{
    int x,t;
}h[MAXN];
bool cmp(D a,D b){
    return a.x<b.x;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&h[i].x);
    for(int i=0;i<n;i++) scanf("%d",&h[i].t);
    sort(h,h+n,cmp); 
    int p=0,tr=0;
    int maxr=h[n-1].x;
    tr=maxr;
    if(tr<h[n-1].t) tr=h[n-1].t;
    p=maxr;
    for(int i=n-2;i>=0;i--){
        int d=p-h[i].x;
        tr+=d;
        if(tr<h[i].t) tr=h[i].t;
        p=h[i].x;
    }
    tr+=p;
    printf("%d",tr);
    return 0;
}