题解：P12643 [KOI 2024 Round 1] 回收退货

· · 题解

大家好我是_S_MY，这是我的第一篇题解。
废话不多说 最好不说，开始做题。
目测算法为模拟加一点点数学，不是很难哈。
模拟分两个部分。
首先，卡车第一次经过所有人家。
假设司机第一趟在摸鱼，经过一户人家，如果还没把东西放出来，好的，直接开溜。不然就顺便把东西带上，用f[i]标记位置x[i]上的货物收了没有。花费的总时间为x[n]（因为是一路开到最后一户不停留）。
第二趟，司机折返。
司机摸完鱼，发现自己还落下了一堆货物。检查f[i]，如果之前没有收的货物已经放出来了，赶紧带上；如果还没放出来，就只能老老实实地等了。总时间为一路走来加等待的时间。
注意：有可能有一些人家第一趟还没把货物放出来，第二趟走到半路就放出来了，不需要等待。
学废了吗？如果还不会，可以看代码。

#include<bits/stdc++.h>
using namespace std;
long long n,x[3001],t[3001],i,l,r,md,tt,f[3001];
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x[i];
        if(x[i]>r) r=x[i];
    }
    for(i=1;i<=n;i++)
        cin>>t[i];
    for(i=1;i<=n;i++)
        if(tt>=t[i]) f[i]=1;//标记已经拿了的货物
    tt=x[n];//一路走来的时间
    if(t[n]>tt) tt=t[n];//回头时的特判，因为必须要等最后一户人家把货物放出来才能掉头
    for(i=n-1;i>=1;i--){//第二趟
        tt+=x[i+1]-x[i];
        if(f[i]!=1) if(tt<t[i]) tt=t[i];
    }
    cout<<tt+x[1];//回到起点
    return 0;
}

完全看懂之后再copy,否则遭天谴