题目链接:http://codeforces.com/contest/427/problem/E

先给出一个经典的模型:货仓选址 (算法竞赛训练指南P29)

在一条数轴上有NN个点,坐标给出,现在要在数轴选择一个点使得这个点到其他点的距离总和d\sum^{}d最小

方法:很显然是将nn个点排序后,选第x2\lceil \frac{x}{2} \rceil 点。
感性的证明:不妨设这个点为 XX 那么设左侧有PP家,右侧有QQ家 若P<QP < Q则将XX往右移那么距离减小QPQ - P,同理可知P>QP > Q类似。

那么此题我们不妨先考虑m=1m = 1的情况,很显然可以发现 他和这个经典模型类似,只是总距离d×2d \times 2

那么当我们考虑mm更大的情况,我们可以发现,相当于从11开始,[1,m],[m+1,2m]...[1, m], [m + 1, 2m]... 每个区间看成一组,那么是不是转化成了刚开始的经典模型?
所以很显然 这样子是等价的。

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
int n,m;
int a[N];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int pos = (n + 1) / 2;
    ll ans = 0;
    for(int i = 1; i <= pos; i += m) {
        ans += a[pos] - a[i];
    } 
    for(int i = n; i >= pos; i -= m) {
        ans += a[i] - a[pos];
    }
    cout << ans * 2;
    return 0;
}