1 条题解
-
1
题解
题目大意
小 Z 的仓库在坐标 处。有 件包裹,第 件要送到 (), 在右侧, 在左侧。
快递车每趟最多装 件,从仓库出发,送完这一趟的包裹后回到仓库。每件包裹只送一次。
求送完所有包裹并回到仓库的最小总路程。
思路分析
1. 左右两侧互不影响
一辆车一趟要么往右走,要么往左走。因为一趟的路线是从 出发沿一个方向送若干包裹再回来,不可能同时往左又往右——如果一趟里既有正坐标又有负坐标的包裹,车要先往一边走、再折返穿过仓库往另一边走,这等价于拆成两趟,路程只会更多。
所以正方向和负方向可以完全独立处理,分别求最小路程后相加即可。
2. 同一侧内怎么贪心
先看正方向。设正方向包裹距离仓库的距离为:
一趟车最多装 件。假设某一趟里装的距离最远的是 ,那么这一趟的路程是:
因为送这趟车必须走到最远的 ,再原路返回。
注意:这一趟的路程只由最远那件决定,其他较近的包裹顺路送掉不影响路程。
于是直觉很明确:每一趟都尽量装 件,并且让最远的 件一起走一趟。
正确性证明
我们证明:把距离按从大到小排序后,每 件一趟,一定最优。
设距离从大到小为:
考虑最远的那件 。它必须被某一趟送掉,这一趟的路程至少是 。既然这一趟一定要走 ,那么在不超过 件的前提下,能顺路多带几件就多带几件,一定不会更差。
因此让 这一趟带上 (若存在),是最优选择。
对剩下的 重复同样论证,得到:按从大到小每 件一趟最优。
负方向完全对称:把 的距离取绝对值后同样处理。
复杂度分析
- 排序:
- 遍历累加:
总时间复杂度 ,空间复杂度 ,可以通过全部数据。
参考代码
#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; }
信息
- ID
- 6
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者