题解

这里用了 WQS 二分，二分队列做法。

const int N = 5e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, m;
	int a[N], s[N];
	ll f[N], sum[N];
	struct node{
		ll x, k;
	}q[N];
	ll w(int l, int r){
		int pos = (l + r + 1) >> 1;
		return (sum[r] - sum[pos]) - a[pos] * 1ll * (r - pos) + a[pos] * 1ll * (pos - l) - (sum[pos] - sum[l]);
	}
	int getG(int i, int j) {
		int l = j, r = n + 1;
		while (l < r - 1) {
			int mid = (l + r) >> 1;
			if (f[i] + w(i, mid) < f[j] + w(j, mid)) l = mid;
			else r = mid;
		}
		return r;
	}
	bool check(int mid) {
		int head, tail;
		q[head = tail = 1] = (node) {0, n + 1};
		for (int i = 1; i <= n; i++) {
			while (head < tail && q[head].k <= i) head++;
			f[i] = f[q[head].x] + w(q[head].x, i) + mid;
			s[i] = s[q[head].x] + 1;
			while (head < tail && getG(q[tail].x, i) <= q[tail - 1].k) tail--;
			q[tail].k = getG(q[tail].x, i);
			q[++tail] = (node){i, n + 1};
		}
		return s[n] > m;
	}
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		sort (a + 1, a + 1 + n);
		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
		ll l = 0, r = 1e10;
		while (l < r-1) {
			int mid = (l + r) >> 1;
			if (check(mid)) l = mid;
			else r = mid;
		}
		check(l);
		printf("%lld\n", f[n] - m * l);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}