https://codeforces.com/contest/571/problem/B
题目大意
给出 $n$ 长的数组 $a$，及某数 $k$，可以任意调整 $a$ 中元素位置，需要最小化
$$ \sum_{i = 1}^{n - k} |a[i] - a[i + k]| $$ 。
问这个最小值是多少。
$2 \le n \le 3 \times 10^5$。$1 \le \min(5000, n - 1)$。$-10^9 \le a[i] \le 10^9$。
简要题解
容易想到，最后就是 $k$ 余数相等的 $k$ 组，每组应该是数组的排序后连续的一段，而且都是单调不增或单调不减排列的。
这 $k$ 条链，长度只有最多两种 $\lfloor n / k \rfloor$ 和 $\lceil n / k \rceil$，且我们知道每种选多少个。
到这里好像我们只会 $O(n k^2)$ 的 DP。（$dp[i][j][l]$ 到 $i$ 位置选了 $j$ 段且其中 $l$ 个长段。）
注意到 $k$ 的限制很奇怪，而且显然上面的 $dp$ 定义有非常多的没用的状态。于是想到我们可以只用选了几段进行转移。$dp[i][j]$ 表示选了 $i$ 段后有 $j$ 个长一点的段。这样我们枚举最后一段是长段还是短段即可，因为我们知道前面长短段选了多少，因此我们也知道终点在哪，就可以推导了。
复杂度
$T$：$O(n \log n + k ^ 2)$
$S$：$O(n + k)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const LL INF = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for (int& i : a) cin >> i;
sort(a.begin(), a.end());
int m = n / k;
int need = n % k;
// cerr << m << ' ' << need << endl;
vector<LL> dp(need + 1, INF);
dp[0] = 0;
for (int ii = 1; ii <= k; ii++) {
for (int i = need; i > 0; i--) {
dp[i] = min(dp[i] + a[ii * m + i - 1] - a[(ii - 1) * m + i],
dp[i - 1] + a[ii * m + i - 1] - a[(ii - 1) * m + i - 1]);
}
dp[0] = dp[0] + a[ii * m - 1] - a[(ii - 1) * m];
// for (int i = 0; i <= need; i++) {
// cerr << dp[i] << ' ';
// }
// cerr << endl;
}
cout << dp[need] << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. Object Identification - Codeforces Round 1004 (Div. 1)