题解 P1368 【均分纸牌（加强版）】

· · 题解

模拟赛的时候被一道以此题为背景的题目坑了，特地过来写个题解，第一次写题解，有不足的地方欢迎指出

这题是P1031均分纸牌的变式，区别在于在该题中纸牌首尾相连，且每次只能移动一张纸牌，但是我们依然可以用贪心的思想来解决（请参考P1031均分纸牌）。

P1031的做法是每次通过与下一堆交换纸牌，把当前堆的纸牌调整为最终状态（平均数），而在本题中纸牌是首位相连的，则一定存在一个位置是最后调整的，使得调整次数最小，我们先不管这个位置具体在哪，先将这个位置设为是K。然后我们构造b[i]=a[i]-ave，其中a[i]为原始数据，ave为原始数据平均数，现在只需要找一种最优方法把b[i]全部调整为0即可：

因为k是最后调整的，我们从k+1堆开始，第i堆需要与i+1堆交换|b[i]|张纸牌可以使得b[i]=0，此时b[i+1]变为b[i+1]+b[i]张纸牌，而i+1堆此时要与i+2堆交换|b[i+1]+b[i]|张纸牌，i+2堆就要与i+3堆交换|b[i]+b[i+1]+b[i+2]|张，像这样往下累加，为了处理方便，我们用S[i]来表示b[i]的前缀和，则上述做法用S[i]来表示就是，第i堆与i+1堆需交换|S[i]-S[k]|张纸牌（这里很重要），那么我们就可以把总的交换次数表示出来了，即 |S[1]-S[k]|+|S[2]-S[k]|+|S[3]-S[k]|+...+|S[n]-S[k]| ① 现在我们就可以根据①式找出k的位置了，我们发现，当S[k]为S数组的中位数时，①式会有最小值，（严格的证明我也不会，你可以去问问数学老师or数竞dalao），我们可以把S数组排序，取S[(n+1)/2]，也就得到S数组的中位数了，我们代入①式我们就得到了最终答案。

下面附上C++的AC代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[1000010];
long long s[1000010],ave,ans,mid; //要用longlong!!
int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) { 
        cin>>a[i];
        ave+=a[i];
        }
    ave/=n; //求平均数
    for(int i=1;i<=n;i++) { s[i]=s[i-1]+a[i]-ave;} //直接构造S[i]
    sort(s+1,s+1+n); 
    mid=s[(n+1)/2]; //排序后取中位数
    for(int i=1;i<=n;i++) ans+=abs(s[i]-mid); //最终答案
    cout<<ans<<endl;
    return 0;
}