33OJ
登录 注册

1 条题解

  • 1
    @ 2026-11-13 23:24:22精华

    题解

    题目大意

    小 Z 的仓库在坐标 00 处。有 nn 件包裹,第 ii 件要送到 xix_i(xi≠0x_i\ne 0),xi>0x_i>0 在右侧,xi<0x_i<0 在左侧。

    快递车每趟最多装 KK 件,从仓库出发,送完这一趟的包裹后回到仓库。每件包裹只送一次。

    求送完所有包裹并回到仓库的最小总路程。

    思路分析

    1. 左右两侧互不影响

    一辆车一趟要么往右走,要么往左走。因为一趟的路线是从 00 出发沿一个方向送若干包裹再回来,不可能同时往左又往右——如果一趟里既有正坐标又有负坐标的包裹,车要先往一边走、再折返穿过仓库往另一边走,这等价于拆成两趟,路程只会更多。

    所以正方向和负方向可以完全独立处理,分别求最小路程后相加即可。

    2. 同一侧内怎么贪心

    先看正方向。设正方向包裹距离仓库的距离为:

    d1≤d2≤⋯≤dmd_1\le d_2\le \cdots\le d_m

    一趟车最多装 KK 件。假设某一趟里装的距离最远的是 dd,那么这一趟的路程是:

    2d2d

    因为送这趟车必须走到最远的 dd,再原路返回。

    注意:这一趟的路程只由最远那件决定,其他较近的包裹顺路送掉不影响路程。

    于是直觉很明确:每一趟都尽量装 KK 件,并且让最远的 KK 件一起走一趟。

    正确性证明

    我们证明:把距离按从大到小排序后,每 KK 件一趟,一定最优。

    设距离从大到小为:

    d1≥d2≥⋯≥dmd_1\ge d_2\ge \cdots\ge d_m

    考虑最远的那件 d1d_1。它必须被某一趟送掉,这一趟的路程至少是 2d12d_1。既然这一趟一定要走 2d12d_1,那么在不超过 KK 件的前提下,能顺路多带几件就多带几件,一定不会更差。

    因此让 d1d_1 这一趟带上 d2,d3,…,dKd_2,d_3,\dots,d_K(若存在),是最优选择。

    对剩下的 dK+1,…,dmd_{K+1},\dots,d_m 重复同样论证,得到:按从大到小每 KK 件一趟最优。 □\square

    负方向完全对称:把 xi<0x_i<0 的距离取绝对值后同样处理。

    复杂度分析

    • 排序:O(nlog⁡n)O(n\log n)
    • 遍历累加:O(n)O(n)

    总时间复杂度 O(nlog⁡n)O(n\log n),空间复杂度 O(n)O(n),可以通过全部数据。

    参考代码

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n,k;
    int a[200005];
    vector<int> x,y;
    int ans;
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin>>n>>k;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]>0) x.push_back(a[i]);
    		else y.push_back(-a[i]);
    	}
    	sort(x.begin(),x.end());
    	sort(y.begin(),y.end());
    	for(int i=x.size()-1;i>=0;i-=k) ans+=2*x[i];
    	for(int i=y.size()-1;i>=0;i-=k) ans+=2*y[i];
    	cout<<ans;
    	return 0;
    }
    
    • 1

    信息

    ID
    6
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及
    标签
    递交数
    3
    已通过
    3
    上传者