解法:数学 + 贪心
时间复杂度:$O(n \times log(n))$
该题首先要推式子:
假设 $a_1$ 给了 $x_1$ 个糖果给 $a_2$,$a_2$ 给了 $x_2$ 个糖果给 $a_3$,一直到 $a_n$ 给了 $x_n$ 个糖果给 $a_1$,其中 $x$ 是具有方向的,正则正向给,负则反向给。
$\to$ 先列出原式:
$f(x)= \begin{cases} a_1-x_1+x_n=b& \\\ a_2-x_2+x_1=b& \\\ … \\\ a_n-x_n+x_{n-1}=b& \\\ \end{cases}$
$\to$ 进一步变形:
$f(x)= \begin{cases} x_1=x_n - (b - a_1)& \\\ x_2=x_n - (2 \times b - a_1 - a_2)& \\\ … \\\ x_{n-1}=x_n-((n - 1) \times b - a_1-a_2 - … - a_{n - 1})& \\\ x_n = x_n - 0\\\ \end{cases}$
而我们所求的答案就是最小化 $\left | x_1 \right | + \left | x_2 \right | + \left | x_3 \right | + … + \left | x_n \right |$ 的值,可进一步带入得到:
$\left | x_n - (b - a_1) \right | + \left | x_n - (2 \times b - a_1 - a_2) \right | + … + \left | x_n-((n - 1) \times b - a_1-a_2 - … - a_{n - 1}) \right | + \left | x_n - 0 \right |$
此时就转变为我们十分熟悉的式子即绝对值不等式,可采用中位数来做。
详见 AcWing 104. 货仓选址 的讲解。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n;
LL s[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
s[i] += s[i - 1];
}
LL b = s[n] / n, ans = 0;
for (int i = 1; i < n; ++i) s[i] = i * b - s[i];
s[n] = 0;
sort(s + 1, s + n + 1);
for (int i = 1; i <= n; ++i) {
ans += abs(s[i] - s[(n + 1) / 2]);
}
cout << ans << endl;
return 0;
}