UVa 11300 Spreading the Wealth——中位数

UVa 11300 Spreading the Wealth——中位数

有n个人，我们要求的是转移硬币的最小值，为此可以求出每个人转移硬币的数量，然后相加便是转移硬币的总数量

设总硬币数为sum，最终每个人都拥有m个硬币（m = sum  / n）

设这n个人所持有的硬币数为ai，每个人给上一个人的硬币数为xi（注意：1.xi可以为负数，2.第一个人给最后一个人 ）

现在我们就要求 |xi| 的最小总和

所以对于第一个人来说： m = a1 - x1 + x2

对于第二个人来说：m = a2 - x2 + x3

..........

变形：

x2 = m  - a1 + x1

x3 = m - a2 + x2 = 2m - a1 - a2 + x1

x4  = m - a3 + x3 = 3m - a1 - a2 - a3 + x1

......

xn = m - an-1 + xn-1 = an - m + x1

x1 = x1(最后这条并不会影响解，可以说没有意义，因此下面就直接忽略掉，这样说其实很笼统，建议读者自己写一下，写一下就明白了)

用ci代替常熟，有：

x2 = x1 - c1

x3 = x1 - c2

x4  = x1 - c3

......

xn = x1 - cn-1

现在要求的就是|x1|,|x1 - c1|, |x1 - c2|, |x1 - c3|...|x1 - cn-1|总和的最小值，这里先给出结论：中位数距离所有顶点的距离之和最小，故x1为c1，c2，c3.....--1的中位数时总和最小

证明的话可以参考训练指南第6页，写得很明白，其实自己画一条数轴也可以推到出来

#include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 1000000 + 10;ll a[maxn], c[maxn], sum, m;int main(){ int n; while (scanf("%d", &n) == 1) { sum = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); sum += a[i]; } m = sum / n; c[0] = 0; for (int i = 1; i <= n; i++) { c[i] = c[i - 1] + a[i] - m; } sort(c, c + n); ll x = c[n / 2], ans = 0; for (int i = 0; i < n; i++) ans += abs(x - c[i]); printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。