사탕 전달

1045: [HAOI 2008] 사탕 전달http://www.lydsy.com/JudgeOnline/problem.php?id=1045 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1416  Solved: 658 [Submit] [Status] Description n 명의 어린이 가 한 바퀴 를 돌 고 각자 ai 개의 사탕 이 있 습 니 다.한 사람 당 좌우 두 사람 에 게 만 사탕 을 전달 할 수 있다.한 사람 이 매번 사탕 하 나 를 전달 하 는 대 가 는 1 이다.
Input 어린이 개수 n 아래 n 줄 ai
Output 은 모든 사람 이 균등 한 사탕 의 최소 대 가 를 받 도록 요구한다.
Sample Input 4 1 2 5 4
Sample Output 4
데이터 규모 30% n < = 1000 100% n < = 1000000
 
사탕 을 교환 하 는 방식 은 1 은 n, 2 는 1, 3 은 2, n 은 n - 1 이다.
ave 는 최종 적 으로 모든 사람 이 가지 기 를 바 라 는 사탕 수 입 니 다.
a [i] i 번 째 사람 이 가 진 사탕 수 를 위해 1 부터 표시 합 니 다.
b [i] 는 i 번 째 사람 이 i - 1 번 에 게 줄 사탕 수 를 나타 내 고 마이너스 로 허용 한다.
첫 번 째 어린이 가 n 번 째 어린이 에 게 사탕 을 준다 고 가정 하면
b[1]=k。
a [1] - b [1] + b [2] = ave (원래 - 보 낸 + 새로 얻 은 = 최종 기대) 에서 얻 은 것:
b[2]=b[1]-a[1]+ave;일반 표현 식 은 b [i] = b [i - 1] - a [i - 1] + ave 입 니 다.통항 공식 은 다음 과 같다.
b[i]=k- (구 화 (아래 표: 1) (위 표 i - 1) (표현 식: a [i]) + (i - 1) * ave;
c [i] = (구 화 (아래 표: 1) (위 표 i) (표현 식: a [i]) - i * ave;
b [i] = k - c [i - 1];
분명히 c [n] = 0 이 있 습 니 다.그러므로 b [1] = k = k + c [n];
총 대 가 는 다음 과 같 습 니 다. )
다음 과 같 습 니 다. (아래 표: 1) (위 표 n) (표현 식: | k - c [i] | );
수축 에 n 개의 점 이 있 는 것 으로 전환 하여 특정한 점 에서 다른 모든 점 의 선분 과 최소 치 를 구 할 수 있 습 니 다.
그러므로 c [] 배열 을 정렬 하여 중위 수 를 찾 으 면 됩 니 다. 짝수 가 있 으 면 중간 두 개 를 취하 면 어느 하나 라 도 됩 니 다.
 

//1045: [HAOI2008]     -ac
//http://www.lydsy.com/JudgeOnline/problem.php?id=1045 
#include 
#include 
using namespace std;
# define M 1000002
long long a[M],c[M];
long long n,ans,ave;
void f_init(){
	ans=0;
}
void f_calc(){
	c[1]=a[1]-ave;
	for(int i=1;i<=n;i++)
		c[i]=c[i-1]+a[i]-ave;
	sort(c+1,c+n+1);
	long long mid=c[n/2];
	for(long long i=1;i<=n;i++)
	  	ans+=abs(mid-c[i]);
	cout<>n){
		f_init();
		long long tmp=0;
		for(int i=1;i<=n;i++)
		 {cin>>a[i];tmp+=a[i];} //     1   
		ave=tmp/n;
		f_calc(); 
	}
	
	return 0;
}