「BZOJ3293」[CQOI2011] 分金币
Description
圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。
Input
第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。
Output
输出被转手金币数量的最小值。
Sample Input
4
1
2
5
4
Sample Output
4
样例解释
设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。
HINT
N<=<=100000,总金币数<=10^9
题解
白书p4
|
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 28 29 30 31 32 33 34 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,a[100001]; long long c[100001]; long long tot,ans; inline int read() { char ch=getchar(); int f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f; } int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); tot+=a[i]; } tot/=n; for(int i=2;i<=n;i++) c[i]=c[i-1]+(a[i-1]-tot); sort(c+1,c+n+1); int tmp=c[(n+1)/2]; for(int i=1;i<=n;i++) ans+=abs(tmp-c[i]); printf("%lld",ans); return 0; } |
Subscribe