1 条题解

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

    样例:

    (0、空载,0→00\to 0。)

    1、载货1,0→40\to 4。

    2、载货2,4→34\to 3。

    3、空载,3→43\to 4。

    4、载货1,4→74\to 7。

    5、空载,7→87\to 8。

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

    首先发现答案一定大于 ∑∣s−t∣\sum|s-t|。多搓几个样例,发现其余的部分就是我们从一个终点走向一个起点所费的距离(把最开始的 00 看作“一个终点”,把最后的 LL 看作“一个起点”),考虑如何最小化,只需把起点坐标和终点坐标分别排序后求出 ∑∣si−ti∣\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;
    }
    

    信息

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