BZOJ 1045: [HAOI2008] 糖果传递

Description

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

Input

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

Output

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

Sample Input

Sample Output

Solution

同BZOJ 3293 分金币，环形均分纸牌。

来自yohaha的题解：

给的这个数据是搞笑的吧…其实只有1e6。

我们令a1， a2…为每个位置初始值，ave为平均值。 x1表示a1 给an的数量， x2表示a2给a1的数量， ……。我们所求即为|x1|+|x2|+…..|xn| 那么显然

a1-x1+x2 = ave -> x2 = ave+x1-a1 = x1-c1(c1 = a1-ave)

a2-x2+x3 = ave　-> x3 = ave+x2-a2 = 2ave+x1-a1-a2 = x1-c2(c2 = 2ave+a1+a2)　….

an-x(n-1)+x1 = ave.

观察可知ci是一个前缀和。

|x1|+|x2|+….|xn|可以变为|x1|+|x1-c1|+|x1-c2|+…|x1-cn|，可以理解为数轴上n个点到c1的距离的和，那么显然应该找中位数。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
LL a[1000005], s[1000005], sum, avg;
int main() {
    int n = getint();
    for (int i = 1; i <= n; ++i) a[i] = getint(), sum += a[i];
    avg = sum / n;
    for (int i = 1; i <= n; ++i) s[i] = a[i] - avg + s[i - 1];
    sort(s+1, s+1+n);
    LL key = s[(n+1) >> 1], ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += abs(key - s[i]);
    printf("%lld", ans);
    return 0;
}