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

· · 题解

我觉得楼下大佬抄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;
}