BZOJ-1045-[HAOI2008] 糖果传递（中位数原理）

Description

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

Input

第一行一个正整数nn<=1'000'000，表示小朋友的个数．

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

Output

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

Sample Input

4
1
2
5
4

Sample Output

题解

这道题对于最终小朋友手中的糖的数量我们是可以算出来的，我们用ave来表示

我们假设G_i表示第i个人给第i-1个人糖的数量，G₁表示第1个人给第n个人

那么最后答案就是|G₁|+|G₂|+···+|G_n|

那么到最后

第一个人的糖就是A₁-G₁+G₂=ave

第二个人的糖就是A₂-G₂+G₃=ave

······

第n个人的糖就是A_n-G_n+G₁=ave

这里我们假设C_i=C_i-1+A_i-ave

所以通过第一个人的糖，我们可以推出G₂=G₁-C₁

通过第二个人，可以推出G₃=G₁-C₂

······

第n个人，可以推出G_n=G₁-C_n-1

所以最后答案就变成了|G₁|+|G₁-C₁|+|G₁-C₂|+···+|G₁-C_n-1|

对于求最后答案，问题就变成了给你坐标轴上的n个点，要你找到一个点，使得这个点到所有的点的距离之和最小

而这个点的坐标就是坐标轴上点的中位数

 #include<bits/stdc++.h>

 #define N 1000005

 #define ll long long

 using namespace std;

 int n,ave;

 ll sum,ans;

 int a[N],c[N];

 int main(){

     scanf("%d",&n);

     for (int i=;i<=n;i++){

         scanf("%d",&a[i]);

         sum+=a[i];

     }

     ave=sum/n;

     for (int i=;i<=n;i++)

         c[i]=c[i-]+a[i]-ave;

     sort(c+,c++n);

     int mid=c[(n>>)+];

     for (int i=;i<=n;i++)

         ans+=abs(mid-c[i]);

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

     return ;

 }

秒客网