题意是一个圆桌上面做了n个人，每个人手头上有不同数目的金币（每个人手头的金币数目已知），然后他们需要通过相互交换来使得大家手头上面的金币数目相等，求最少流通值。
白书上面用了一个非常强劲的代数做法，觉得这个思想还是需要学习一下的。
因为人数和总的金币数是确定的，而且题目确保了一定除得进，所以最终情况下每个人手头的钱币数量是确定的，设为M，把人编号1,2,3,4，..n，设xi为编号i-1的人给编号为i的人的金币数，我们最终要求的值即为|x1|+|x2|+…+|xn|，Ai为每个人初始状况下手头的钱币数，有
A1+x1-x2=M → x2=A1-M+x1
A2+x2-x3=M → x3=A2-M+x2 → x3=A2-M+A1-M+x1
A3+x3-x4=M → x4=A3-M+x3 → x4=A3-M+A2-M+A1-M+x1
….
An+xn-x1=M → x1=An-M+…..A1-M+x1
设Ci为M-Ai即每个人手头的金币数和期望数目的差值,Si=C1+C2+…+Ci，那么上面的式子可以化为
x2=x1-S1
x3=x1-S2
x4=x1-S3
……
xn=x1-Sn-1
x1=x1-Sn 即Sn=0这个结论显然是对的
现在|x1|+|x2|+|x3|+….+|xn|=|x1-S1|+|x1-S2|+|x1-S3|+|x1-S4|+…..+|x1|
抽象转化为这么一个问题，数轴上面有一串点，我们要找一个点x1使得这个点到数轴上所有已有点的距离最小，并求出这个距离。
结论是这个点是中位数。可以先猜测后证明，证明很简单，讨论n，若n为奇数，那么最后取得点是最中间的点，两边各有(n-1)/2个点，如果移动一个很小的量d，那么必然新的点两边的点的数目不相等了，必定比原来大d，因此最优就不成立了。而n为偶数的时候，中位数是最中间两个点的中间，如果移动这个点，只要没有越过最中间两个点的任意一个，那么总距离的值不会发生变化，如果越过了任意一个，必定导致两边的点数不相等，总距离值变大。因此的证，x1就应该是数列S1,S2,….Sn的中位数，然后计算|x1-S1|+|x1-S2|+|x1-S3|+|x1-S4|+…..+|x1|就好
解这道题目用的代数思路非常的巧妙，不看书我实在是想不出来。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 |
#include <cstdio>#include <cstring>#include <algorithm>typedef
long
long
LL;using
namespace
std;const
int
maxn = 1000001;int
A[maxn];LL C[maxn];int
main() { int
n; while(~scanf("%d",&n)) { LL sum = 0,ans = 0,std; for(int
i = 0;i < n;i++) { scanf("%d",&A[i]); sum += A[i]; } sum /= n; C[0] = A[0] - sum; for(int
i = 1;i < n;i++) C[i] = A[i] - sum + C[i - 1]; sort(C,C + n); if(n & 1) std = C[n / 2]; else
std = (C[n / 2] + C[n / 2 - 1]) / 2; for(int
i = 0;i < n;i++) ans += abs(std - C[i]); printf("%lld\n",ans); } return
0;} |
UVA 11300 Spreading the Wealth
原文：http://www.cnblogs.com/rolight/p/3538971.html