1045: [HAOI2008] 糖果传递

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2975 Solved: 1327

[Submit][Status][Discuss]

Description

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

Input

小朋友个数n 下面n行 ai

Output

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

Sample Input

4

1

2

5

4

Sample Output

4

HINT

100% n<=987654321

（这个数据范围加了特技，真实范围n<=1000000,Duang）

数学题，可以说是**均分纸牌**的环状问题

首先数组get【i】表示第i个小朋友从第i+1个小朋友那里得到的糖果，可正可负

所以也可以表示第i+1个小朋友给第i个小朋友的糖果，即第i+1个小朋友失去的数量

所以我们不难得出：

candy【i】+get【i】-get【i-1】=pj（平均）

这一步并不足以求解

所以移项可得：

get【i】=pj-candy【i】+get【i-1】

上述式子可以推出get的值，那么问题在于从哪里开始最小

问题为圆环，最小想到距离，距离想到中位！！

于是…..A之

代码精炼至极：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

#define maxn 1000002

long long candy[maxn]={0};

long long get[maxn]={0};

int main()

{

    int n;

    long long sum=0,pj=0;

    long long ans=0;

    scanf("%d",&n);

    for (long long i=1; i<=n; i++)

        {

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

            sum+=candy[i];

        }

    pj=sum/n;

    for (long long i=1; i<=n; i++)

        get[i]=get[i-1]+pj-candy[i];

    sort(get+1,get+n+1);

    long long mid=get[(1+n)/2];

    for (long long i=1; i<=n; i++)

        ans+=fabs(mid-get[i]);

    printf("%lld",ans);

    return 0;

}