【bzoj1045】[HAOI2008] 糖果传递

2015.04.14 19:36 Tue | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

小朋友个数n 下面n行 ai

Output

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

Sample Input

4
1
2
5
4

Sample Output

4

HINT

数据规模
30% n<=1000
100% n<=100000

Source

看起来挺水的题考试的时候楞是1分没拿。。一直在研究什么最优匹配什么的,最后暴力写的是费用流,光荣的全部TLE……
考完试看了题解之后发现我的思路实在是差的有点远……
设A[i]为第i个人给第i-1个人的糖果数,默认第0个人为第n个人。
之后可以列出方程组,设没人平均分配的糖果数为 x
x-a[1]=A[2]-A[1]    A[2]=A[1]+x-a[1]
x-a[2]=A[3]-A[2]   A[3]=A[1]+2x-a[1]-a[2]
以此类推……
我们要维护的就是每行第二个等式右端的绝对值之和,使其最小。初中就应该学过,数轴上一堆数,离他们的距离之和最小的点就是这些数的中位数或者一段中位区间,于是随便搞一下就行了。

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 1000100
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
ll a[maxn],c[maxn],sum;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++) c[i]=a[i]-sum,c[i]+=c[i-1];
    sort(c+1,c+n+1);
    ll tmp=c[(n+1)>>1],ans=0;
    for(int i=1;i<=n;i++) ans+=labs(tmp-c[i]);
    printf("%lld\n",ans);
}```