uva11300Spreading the Wealth<数学>

链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2275

思路

原来金币数为a1,a2,`````an;

最终的金币为这些数的平均值，设为M

xi表示i给i+1的金币个数

a1+xn-x1=M
a2+x1-x2=M
a3+x2-x3=M
a4+x3-x4=M
.......
an+x(n-1)-xn=M
利用后面n-1个等式，用x1表示 x2,x3,...xn
x2=x1-(M-a2)
x3=x1-(2*M-a2-a3);
....

结果就是求|x1|+|x1-b1|+|x1-b2|+...+|x1-b[n-1]|的最小值，取中位数;

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 typedef long long LL;
 9 int N;
10 LL c[1000005], sum, M, a;
11 LL Labs(  LL a )
12 {
13     return a>0?a:-a;
14 }
15 int main( )
16 {
17     while( scanf("%d", &N )!= EOF ){
18         sum=0, c[0]=0;
19         for( int i=1; i<=N; ++ i ){
20             scanf( "%lld", &a );
21             sum+=a;    
22             c[i]=sum;
23         }
24         M=sum/N;
25         sum=0;
26         for( int i=1; i<=N; ++ i ){
27             c[i]-=i*M;
28         }
29         sort( c, c+N );
30         M=c[N/2];
31         for( int i=0; i<N; ++ i ){
32             c[i]-=M;
33             sum+=Labs(c[i]);
34         }
35         printf( "%lld\n", sum );
36     }
37     return 0;
38 }