Time Limit: 10 Sec Memory Limit: 162 MB Submit: 4847 Solved: 2436 [Submit][Status][Discuss] Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn<=1’000’000，表示小朋友的个数． 接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数． Output
求使所有人获得均等糖果的最小代价。 Sample Input 4
1
2
5
4 Sample Output 4
解题思路
此题跟均分纸牌很像，只是形成了一个环。所以如果直接枚举的时间复杂度是O(n^2)，显然会T，所以找规律。sum[i]为a[i]-ave的前缀和。如果我们选取一点p为初始点，可以列出以下式子： a[p] =sum[p] a[p+1]=sum[p+1]-sum[p] … a[n]=sum[n]-sum[p] a[1]=sim[1]-sum[p] .. 所以答案就为(sum[i]-sum[p]) 1<=i<=n (如果不知道的话去做做均分纸牌） 要使答案最小，当sum[p]为中位数时即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN =
1e6+
5;
inline int rd(){
int x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)) {
if(ch==
'-')f=-
1;ch=getchar();}
while(
isdigit(ch)) {x=(x<<
1)+(x<<
3)+ch-
48;ch=getchar();}
return x*f;
}
int n,a[MAXN];
LL sum[MAXN],ave;
LL ans;
int main(){
n=rd();
for(
register int i=
1;i<=n;i++) a[i]=rd(),ave+=a[i];
ave/=n;
for(
register int i=
1;i<=n;i++) a[i]-=ave,sum[i]=sum[i-
1]+a[i];
sort(sum+
1,sum+
1+n);
LL t=sum[(n+
1)>>
1];
for(
register int i=
1;i<=n;i++)
ans+=
abs(t-sum[i]);
printf(
"%lld",ans);
return 0;
}
