自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:55:36，当前版本为作者最后更新于2018-04-17 21:00:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

$\quad\quad$贪心+数学

$\quad$先来讲下普通均分纸牌问题：

普通均分纸牌问题就是$n$个小朋友排成一列，各自有$a[i]$张牌，每个人只能给相邻的人传递纸牌，问至少需要传递多少张纸牌才能使每个小朋友牌的个数相等。

设总牌数为$sum$（即$sum=\sum{a[i]}$），则每个人最后会各自有$T=\frac{sum}{n}$张牌，设$g[i]=T-a[i]$，则让前$k$个人牌数相同需要的交换牌数为$\sum\limits_{i=1}^{i\leq k}{|s[i]|}$，其中$s[i]=\sum\limits_{j=1}^{j\leq i}{g[i]}$，可以这样理解，要让前$k$个人牌数相同，要依次让前$1,2,3…k-1$个人牌数相同，多退少补，会与后边的人发生二者之差绝对值的牌数交换。所以移动总牌数$ans=\sum{|s[i]|}$。

再来讲下本题的环形均分纸牌问题：

环形均分纸牌问题就是$n$个小朋友围成了一圈（等同于第一人和最后一人相邻），这样的话其实可以同样的处理。

仔细思考环形均分纸牌问题可以发现一个性质：必定至少有两个相邻的人不需要从别人那里获得纸牌（这是显然的，不妨设这两个人的位置为$i$和$i+1$，则环形序列中必定有满足条件$a[i]\leq T\;\;a[i+1]\geq T$的两个相邻位置，这样$a[i],\;a[i+1]$之间没有交换，$a[i]\leq T$可以从$a[i-1]$获得纸牌，$a[i+1]\geq T$可以把多的纸牌给$a[i+2]$）。

于是由上面的性质，我们直接破环成链，枚举相邻的不需要交换纸牌的两人（将其分别放在第一和最后一个位置）。

按开始的序列顺序，像普通均分纸牌一样处理出$s$数组，那么假设枚举的位置为$k$，则类比普通均分纸牌求法，新的$s[i]=s[i]-s[k]$（注意$s$为前缀和），于是$ans=\sum{|s[i]-s[k]|}$，我们套用中学数学知识可知当$s[k]$为$s$中位数时，$ans$最小。于是本题就解决了。

$\quad$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处）

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=105;
ll n,a[N],sum,s[N];
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i];
    sort(s+1,s+n+1);
    sum=0;
    for(int i=1;i<=n;i++)sum+=abs(s[n/2+1]-s[i]);
    cout<<sum;
    return 0;
}