【BZOJ 1045】 1045: [HAOI2008] 糖果传递

时间：2022-06-13 16:45:11

1045: [HAOI2008] 糖果传递

Description

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

Input

　　第一行一个正整数n<=987654321，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的
糖果的颗数．

Output

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

Sample Input

4
1
2
5
4

Sample Output

4
 
 
【分析】
　　一道经典题。
　　设xi为i给i-1多少个糖果（负的表示反向给），x1表示1给n多少个糖果。
　　设M为平均数。
　　有：
　　a1-x1+X2=M -> x2=M-a1+x1
　　a2-x2+x3=M -> x3=M-a2+x2=2M-a1-a2+x1
　　.....
　　an-xn+x1=M
　　观察一下，设ci=ai-M
　　则：
　　x2=x1-c1
　　x3=x1-c2
　　...
　　就是求|x1|+|x1-c1|+|x1-c2|+...+|x1-cn-1|的最小值，变成了经典的数学的绝对值不等式的题目。
　　在数轴上表示成点到点的距离，就知道x1取所有C的中位数既有最小值。
 
 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define Maxn 10000010

 #define LL long long

 LL a[Maxn],c[Maxn],M;

 LL myabs(LL x) {return x>?x:-x;}

 int main()

 {

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     M=;

     for(int i=;i<=n;i++) M+=a[i];

     M/=n;

     c[]=;

     for(int i=;i<n;i++) c[i]=c[i-]+a[i]-M;

     sort(c,c+n);

     LL now=c[n/],ans=;

     for(int i=;i<n;i++) ans+=myabs(c[i]-now);

     printf("%lld\n",ans);

     return ;

 }

%%%大颓果

2016-12-13 16:53:51

相关文章