[BZOJ3293] [Cqoi2011] 分金币 (贪心)

2022-07-09 18:49:02

Description

　　圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

Input

　　第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

Output

　　输出被转手金币数量的最小值。

Sample Input

4
1
2
5
4

Sample Output

　　样例解释
　　设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。

HINT

　　N<=100000,总金币数<=10^9

Source

Solution

　　同$BZOJ1045$，数据范围还小了不少，，，题解在这

 #include <bits/stdc++.h>

 using namespace std;

 long long a[], s[];

 int main()

 {

     int n;

     long long ave = , ans = ;

     scanf("%d", &n);

     for(int i = ; i <= n; ++i)

         scanf("%lld", a + i);

     for(int i = ; i <= n; ++i)

         ave += a[i];

     ave /= n;

     for(int i = ; i <= n; ++i)

         s[i] = s[i - ] + a[i] - ave;

     sort(s + , s + n + );

     for(int i = ; i < n /  + ; ++i)

         ans += s[n /  + ] - s[i];

     for(int i = n /  + ; i <= n; ++i)

         ans += s[i] - s[n /  + ];

     printf("%lld\n", ans);

     return ;

 }

码农公寓