LOJ 10010 糖果传递

发表于 更新于 分类于

糖果传递

设\(x-i\)表示第\(i\)个人向第\(i-1\)传递的糖果数，\(i\in [1,n],x-i\in \mathjaxbb{z}\)
特别的\(x-1\)表示\(1\)向\(n\)传递的糖果数。

设平均数为\(q\)
\(a-i-x-i+x_{i+1}=q\) 则有\(x-i-x_{i+1}=a-i-q\)

\(x-1-x-2=a-1-q\)
\(x-2-x-3=a-2-q\)
\(......\)
\(x_{n-1}-x_{n}=a_{n-1}-q\)

实际上还有\(x-n-x-1=a-n-q\)，但是这个方程并没有什么意义。
我们把每个方程相加，可以得到： \(x-1=x-n+\sum_{i=1}^{n-1}a-i-q\)
\(x-2=x-n+\sum_{i=2}^{n-1}a-i-q\)
\(......\) \(x_{n-1}=x_{n}+a_{n-1}-q\)

把\(\sum a-i-q\)看作常数
题目求 \(\lvert x-n+t-1\rvert+\lvert x-n+t-2\rvert+...+\lvert x-n+t_{n-1}\rvert+\lvert x-n\rvert\)
为了形式统一，可以把\(\lvert x-n\rvert\)变成\(\lvert x-n\rvert-t-n,t-n=0\)

这是一个经典的结论，当\(x-n\)取\(t\)中位数时最小。
具体证明是\(\lvert x+t\rvert\)看作坐标轴上两点距离。
因为有\(\lvert x-a\rvert+\lvert x-b\rvert\geq \lvert a-b\rvert\)调整\(x\)取值，发现在中位数的时候最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 5;
ll n, sum[N], t[N], b[N], ans;

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
    ll qaq = sum[n] / n;
	for (int i = 1; i < n; i++) {
        t[i] = sum[n - 1] - sum[i - 1] - (n - i) * qaq;
		t[i] = -t[i];
		b[i] = t[i];
	}
	t[n] = 0;
	b[n] = 0;
	sort(t + 1, t + n + 1);
	ll xn = t[n / 2];
	for (int i = 1; i <= n; i++) ans = ans + abs(xn - b[i]);
	printf("%lld\n", ans);
	return 0;
}