题解 P2512 【[HAOI2008]糖果传递】

2018-02-13 15:19:00


我觉得楼下大佬抄hzwer不太好吧

虽说我大概是抄进阶指南

首先这道题是一个模型,我们称之为环形均分纸牌。显然这个模型是出自luogu1031那道均分纸牌,没有过的可以先过一下。

先来看不是环形的情况。

假设总和为 $T$ ,有 $M$ 张纸牌。设 $ave = \dfrac{T}{M}$ 。对于第i个人来说,如果 $C[i] < ave$ 他拿的应该是 $C[i] + ave$ 张,后一个拿 $C[i + 1] - ave + C[i]$ ,否则,他拿 $C[i] - ave$ 张,而后一个拿 $C[i + 1] + C[i] - ave$ 张。

但是这样并不方便维护,我们考虑整体和隔离的思想。将前i个看做一个整体,显然前i个内部的均分是不会改变其整体结构的,因而对于该体系来说,想要达到平均数结构,就必须与下一个体系交换足够的纸牌,而交换数量就是 $|G[i] - i \cdot ive|$ ,其中 $G[i]$ 是前缀和。然后就可以推出一个结论: $d = \sum ^M _{i = 1} |i \cdot ave - G[i]|$ ,也就是将每次体系更新的贡献加起来。

如果让每个人的数量都减去 $ave$ ,结果就可以经过简单的数学推导进一步化简: $d = \sum ^M _{i = 1} |S[i]|$ ,其中 $S[i]$ 是新数组的前缀和。这就是均分纸牌问题的通用公式。

现在考虑一种变形:如果这里的纸牌是环形的呢?

对于环形问题,首先考虑切开。假定我们切开的东西是 $A[k + 1], A[k + 2], ..., A[M], A[1], ..., A[k]$ ,那么其前缀和也会有所变化,即 $S[k + 1] - S[k], S[k + 2] - S[k], ..., S[M] - S[k], .S[1] + S[M] - S[k], ..., S[M]$

由于均分之后, $S[M] = 0$ 恒成立,所以前缀和的变化仅仅是减去 $S[k]$ 。那么,我们要求的就是哪个取值上最短,换言之,求什么时候 $\sum^M_{i = 1} |S[i] - S[k]|$ 取到最小。

因而,这里我们要求的东西是 $\sum^M_{i = 1} |S[i] - S[k]|$ 的最小值。答案是在中位数处取到,原因各位可以想象将 $S[i]$ 投影到一个坐标平面内。然后我们用一条线去扫,点到线的距离之和就是上面的式子的最小值。从中位数的位置变化到靠下的位置或是靠上的位置,都会使某一部分点的距离增大。所以这里转化为求中位数,也就是求第 $\dfrac{n + 1}{2}$ 大元素,由于 $N \leq 10^6$ 所以不建议排序(虽然也能用)。我们可以用STL的kth_elements()函数O(n)求出k大。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

LL sum[1000003], S; 

inline void read(LL &x) {
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
int main() {
    LL n, ans = 0;
    read(n);
    for(int i = 1; i <= n; ++i) read(sum[i]), S += sum[i];
    LL ave = S / n;
    for(int i = 1; i <= n; ++i) sum[i] -= ave;
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + sum[i];
    int m = (n + 1) / 2;
    nth_element(sum + 1, sum + m, sum + n + 1);
    for(int i = 1; i <= n; ++i) ans += abs(sum[i] - sum[m]);
    cout<<ans<<endl;
    return 0;
}