\(设x_{i}为第i个同学从第i-1个同学获得的糖果数，若x_{i} < 0，则第i-1个同学从第i个同学获得-x_{i}个糖果\)
\(特别地，x_{1}为第1个同学从第n个同学获得的糖果数\)
\(均分后，每个同学拥有的糖果为avg = \frac{\sum_{i = 1}^{n}a_{i}}{n}，则\)
$$avg = a_{1}+x_{1}-x_{2} \\ avg = a_{2}+x_{2}-x_{3} \\ … \\ avg = a_{n}+x_{n}-x_{1}$$
\(改写一下，有\)
$$x_{2} = avg-a_{1}+x_{1} \\ x_{3} = avg-a_{2}+x_{2} = 2avg-a_{1}-a_{2}+x_{1} \\ … $$
\(记c_{i}=\sum_{j=1}^{i}a_{j}-iavg，则有\)
$$x_{i} = x_{1}-c_{i}$$
\(问题所求的代价则为\sum_{i=1}^{n}|x_{1}-c_{i}|，要使其最小，则x_{1}为c_{i}的中位数\)
\(用STL中的nth_element()求中位数，复杂度O(n)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<stdio.h> #include<algorithm> #include<math.h> #define MAXN 1000010 using namespace std; int n; long long sum, c[MAXN], a[MAXN], avg, tot; int main() { scanf("%d", &n); for (int i = 1, x; i <= n; ++i) { scanf("%lld", &a[i]); sum += a[i]; } avg = sum/n; for (int i = 2; i <= n; ++i) c[i] = c[i-1]+a[i]-avg; int mid = n >> 1 | 1; nth_element(c+1, c+mid, c+n+1); for (int i = 1; i <= n; ++i) tot += abs(c[i]-c[mid]); printf("%lld", tot); return 0; } |