[HAOI2008]糖果传递

题目描述

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

输入输出格式

输入格式：

小朋友个数n 下面n行 ai

输出格式：

求使所有人获得均等糖果的最小代价。

输入输出样例

输入样例#1:

4
1
2
5
4
输出样例#1:
4

说明

对于100%的数据 (n<=10^6)

题解

环形均分纸牌

先考虑线性的均分纸牌是怎么做的

先求出平均值ave

然后将每堆的牌数-ave

表示需要增加/扔出多少张纸牌

然后求一个前缀和Sum

把n个前缀和加起来就是答案了

那么环形的均分纸牌也是类似

只是我们要考虑破环为链

那么我们就是要求(sum_{i=1}^{n}{Sum[i]-Sum[t]})最小

这个(t)显然就是所有(Sum[])的中位数所对应的位置

代码

#include<cstdio>
#include<algorithm>
# define LL long long
const int M = 1000005 ;
using namespace std ;
inline LL read() {
	char c = getchar() ; LL x = 0 , w = 1 ;
	while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
	while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
	return x*w ;
}

int n , mid ;
LL v[M] , ave , sum[M] , Ans ;
int main() {
	n = read() ; mid = (n + 1) >> 1 ;
	for(int i = 1 ; i <= n ; i ++) 
	    v[i] = read() , ave += v[i] ;
	ave /= n ;
	for(int i = 1 ; i <= n ; i ++) v[i] -= ave ;
	for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + v[i] ;
	nth_element(sum + 1 , sum + mid , sum + n + 1) ;
	for(int i = 1 ; i <= n ; i ++) Ans += abs(sum[i] - sum[mid]) ;
	printf("%lld
",Ans) ;
	return 0 ;
}