[KOI 2024 Round 1] 回收退货

Ghosty_Neutrino · 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;
}