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();
}