uva11300Spreading the Wealth
5981 ワード
リンク:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2275
構想
もとは金貨の数はa 1で、a 2、````an;
最終的な金貨はこれらの数の平均値をMとする
xiはi+1の金貨の個数を表す
View Code
構想
もとは金貨の数はa 1で、a 2、````an;
最終的な金貨はこれらの数の平均値をMとする
xiは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
", sum );
36 }
37 return 0;
38 }