1 条题解

  • 1
    @ 2026-9-5 14:38:25

    样例:

    (0、空载,000\to 0。)

    1、载货1,040\to 4

    2、载货2,434\to 3

    3、空载,343\to 4

    4、载货1,474\to 7

    5、空载,787\to 8

    1、2、4 是必不可少的,观察 0、3、5。

    首先发现答案一定大于 st\sum|s-t|。多搓几个样例,发现其余的部分就是我们从一个终点走向一个起点所费的距离(把最开始的 00 看作“一个终点”,把最后的 LL 看作“一个起点”),考虑如何最小化,只需把起点坐标和终点坐标分别排序后求出 siti\sum|s_i-t_i| 即为多余量最小值。

    #include<iostream>
    #include<algorithm>
    #include<vector>
    #define int long long
    using namespace std;
    const int N=1e5+7;
    int n,m,a[N],b[N],ans;
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i]>>b[i];
    		ans+=abs(a[i]-b[i]);
    	}
    	a[0]=m;
    	b[0]=0;
    	sort(a,a+n+1),sort(b,b+n+1);
    	for(int i=0;i<=n;i++){
    		ans+=abs(a[i]-b[i]);
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 1

    信息

    ID
    829
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    22
    已通过
    7
    上传者