「BZOJ3293」[CQOI2011] 分金币

2014年5月8日3,9760

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

#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;
}

#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;

}

« 「POJ2356」Find a multiple 「BZOJ1603」[Usaco2008 Oct] 打谷机 »

hzwer.com _ Home | http://hzwer.com

「BZOJ3293」[CQOI2011] 分金币

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论