UVa 11300 Spreading the Wealth

　　这道题自己分析时觉得挺麻烦的，没分析出来，只好看《训练指南》了，自己的分析和建模能力还是太弱了。

　　代码如下：

View Code

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 1000000+10;
 6 long long a[maxn], c[maxn];
 7 
 8 int main()
 9 {
10 #ifdef LOCAL
11     freopen("in", "r", stdin);
12 #endif
13     int n;
14     while(scanf("%d", &n) != EOF)
15     {
16         long long sum = 0;
17         for(int i = 0; i < n; i++)
18         {
19             scanf("%lld", &a[i]);
20             sum += a[i];
21         }
22         long long aver = sum / n;
23         c[0] = 0;
24         for(int i = 1; i < n; i++)
25             c[i] = c[i-1] + a[i] - aver;
26         sort(c, c+n);
27         long long ans = 0;
28         for(int i = 0; i < n-1-i; i++)
29             ans += (c[n-1-i]-c[i]);
30         printf("%lld\n", ans);
31     }
32     return 0;
33 }

　　下面是不保存a数组的代码：

View Code

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 1000000+10;
 6 long long c[maxn];
 7 
 8 int main()
 9 {
10 #ifdef LOCAL
11     freopen("in", "r", stdin);
12 #endif
13     int n;
14     long long a;
15     while(scanf("%d", &n) != EOF)
16     {
17         long long sum = 0;
18         c[0] = 0;
19         for(int i = 0; i < n; i++)
20         {
21             scanf("%lld", &a);
22             if(i)   c[i] = c[i-1] + a;
23             sum += a;
24         }
25         long long aver = sum / n;
26         for(int i = 1; i < n; i++)
27             c[i] -= aver*i;
28         sort(c, c+n);
29         long long ans = 0;
30         for(int i = 0; i < n-1-i; i++)
31             ans += (c[n-1-i]-c[i]);
32         printf("%lld\n", ans);
33     }
34     return 0;
35 }