经数学分析,能将该题转化为找中位数的问题,即货仓选址问题
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int a[N];
LL s[N], c[N]; //s为前缀和数组
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &s[i]);
s[i] += s[i - 1]; //求前缀和
}
LL avg = s[n] / n; //平均值
//至少存在一个多余方程,故至多只有n-1个独立方程,所以此处省略一个
for (int i = 2; i <= n; i ++ ) c[i] = (i - 1) * avg - (s[i] - s[1]); //上图公式求c1 ~ cn
//下面的步骤跟货仓选址相同
sort(c + 1, c + n + 1);
LL mid = c[n + 1 >> 1];
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += abs(c[i] - mid);
printf("%lld\n", res);
return 0;
}