[Codeforces] CF1591C Minimize Distance

CF1591C Minimize Distance

题目

一条线上有 \(n\) （\(1 \le n \le 2 \cdot 10^5\)）个仓库，第 \(i\) 个仓库的位置是 \(x_i\) （\(1 \le i \le n\)）。

你有 \(n\) 箱货物，要分别运到这 \(n\) 个仓库里。你的初始位置在点 \(0\) ，一次可以携带 \(k\) （\(1 \le k \le n\)） 箱货物。在送完携带的所有货物后，需要返回点 \(0\) 去取货物。

请求出送完所有货物时走的最短路程。

样例输入

4
5 1
1 2 3 4 5
9 3
-5 -10 -15 6 5 8 3 7 4
5 3
2 2 3 3 3
4 2
1000000000 1000000000 1000000000 1000000000

样例输出

25
41
7
3000000000

思路

首先来画幅图：

那么，最优策略肯定是每次都那尽量多的货物出发，当货物没了之后再回到原点取货：

但是假如剩余的仓库小于\(k\)个呢？

不难发现，即便是此时，上述方法依然是最优的，但同时也是唯一的

所以整体思路就这么定下来了

然后发现，其实在最后一次送货之后是没必要再返回原点地，而最后一次送货有可能去\(a[n]\)，也有可能去\(a[1]\)（这里假定\(a\)数组天然递增）

那么整个的最优解就需要再减掉一个\(max\{a[n],|a[1]|\}\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int n,k,ans,now;
int a[Maxn];
void run()
{
	cin>>n>>k;ans=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n && a[i]<0;i+=k) ans+=2*abs(a[i]);
	for(int i=n;i>=1 && a[i]>0;i-=k) ans+=2*abs(a[i]);
	cout<<ans-max(abs(a[1]),abs(a[n]))<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run();
}