题解：P11940 [CrCPC 2024] 搬东西

Needma · 2025-03-28 17:40:14 · 题解

问题描述

街道上有一些家商店，自西向东编号为 1, 2, \cdots, l，相邻两家商店的距离为 1 米。有 n 个任务，第 i 个任务要求从商店 s_i 搬东西到商店 t_i。假设一次可以搬无限重的东西，可以从任意商店出发，整个任务结束后可以停在任意商店，需要求出路程和的最小值。

看到题，感觉可以用贪心，发现在每个区间内，如果向左的方案等与向右的方案，我们可以按块合并处理，然后正反都扫一次就好了。

计算路程可以这样保证最优秀：

long cur=mn;
for(auto[s,e]:iv){
    ans=min(ans,2*(mx-mn)+cur-s);
    cur=min(long(e),cur+2*(e-s));
}

原理：2 * (mx - mn) 是在 mn 到 mx 范围内往返一次的基础路程。cur 表示当前的最佳位置，s 是反向区间的起点，cur - s 是从最佳位置到当前区间起点的额外路程。通过不断更新 ans 取最小值，能找到全局最小路程。同时，更新 cur 为当前区间终点 e 和 cur + 2 \times (e - s) 中的较小值，确保 cur 始终是最优的。

ac code：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int l,n; cin>>l>>n;
    vector<pair<int, int>> t(n);
    for(auto&[s,e]:t) cin>>s>>e;
    long ans=LONG_MAX;
    for(int i=0;i<2;++i){
        int mn=INT_MAX,mx=INT_MIN; vector<pair<int, int>> ev;
        for(auto[s,e]:t){mn=min(mn,min(s,e));mx=max(mx,max(s,e));
            if(s>e){ev.emplace_back(s,1);ev.emplace_back(e,-1);}
        }
        sort(ev.begin(),ev.end()); int b=0,st;
        vector<pair<int, int>> iv={{mn,mn}};
        for(auto[p,c]:ev){if(!b) st=p; b+=c; if(!b) iv.emplace_back(st,p);}
        iv.emplace_back(mx,mx); long cur=mn;
        for(auto[s,e]:iv){ans=min(ans,2*(mx-mn)+cur-s);cur=min(long(e),cur+2*(e-s));}
        for(auto&[s,e]:t) s=-s,e=-e;
    }
    cout<<ans<<endl; return 0;
}