自动搬运

查看原文

来自洛谷，原作者为

	Needna Think Twice Code Once.

搬运于2025-08-24 23:11:30，当前版本为作者最后更新于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;
}