HLG2081分苹果

苹果

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 39(24 users) Total Accepted: 29(22 users) Rating: Special Judge: No

Description

圆桌旁围坐n个人，按顺序将他们编号为1~n，第i个人有xi个苹果(i=1,2,...,n）。苹果的总数量为A。数据保证A为n的倍数，且v=A/n。 每个人可以给左右相邻的人苹果，直到每个人手上的苹果数为平均值v。 输出需要转移的苹果数量的最小值。

Input

有多组测试数据。 每组测试数据的第一行为正整数n（n<=10^6），接下来有n行，每行一个整数，逆时针给出初始状态每人手中的苹果数xi。 处理到文件结束。

Output

对每组测试数据，输出转移苹果数量的最小值，每组一行。数据保证输出为64位无符号整数范围内。

Sample Input

3 100 100 100 4 1 2 5 4

Sample Output

0 4

Source

"科林明伦杯"哈尔滨理工大学第四届ACM程序设计竞赛（预选赛）

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; /* 能两边给，那么x1可以给x2，x2也可给x1，绝对值就是|x1-x2|，我们假设逆时针顺序x2给x1，就相当于x2给了x1了a2（a2正负都OK）个苹果，那个x1就有：A1+a2-a1=m,A2+a3-a2=m...... a2=m-A1+a1 a3=m-A2+a2=2m-A1-A2+a1 a4=3m-A1-A2-A3+a1....... 由于A1，A2和m都是给定的，所以影响的只有a，也就是指a1. Ci指Ai-M 那么a2=a1-C1,a3=a1-C2,a4=a1-C3 使ai的绝对值最小，则转换成一条直线上的点到某点上的距离之和最小的问题 则a1为这些数的中位数 */ int A[1000001],C[1000001]; int main() { int n,sum; while(~scanf("%d",&n)){ long long int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&A[i]); sum+=A[i]; } int v=sum/n; /*计算Ci，写写方程代代看看*/ C[0]=0; for(int i=1;i<=n;i++) { C[i]=A[i]-v+C[i-1]; } /*求和*/ sort(C+1,C+1+n); long long int s=0; for(int i=1;i<=n/2;i++) { s=s+C[n+1-i]-C[i]; } printf("%lld\n",s); } return 0; }

#include<stdio.h> #include<string.h> #include<iostream> #include<math.h> #include<algorithm> using namespace std; int a[1000005],c[1000005]; int main() { int n; while(scanf("%d",&n)!=EOF) { long int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum=sum+a[i]; } int m=sum/n; c[0]=0; for(int i=1;i<=n;i++) c[i]=m+c[i-1]-a[i]; sort(c+1,c+n+1); long int num=0; int temp=c[n/2+1]; for(int i=1;i<=n;i++) { num=num+abs(c[i]-temp); } printf("%ld\n",abs(num)); } return 0; }