均分纸牌有三种情况：线性，环形，二维
@[toc]

线性

题目描述

P1031 均分纸牌
有N堆纸牌，编号分别为1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。
移动规则:只能向相邻的纸牌移动
问最少移动多少次可以使纸牌数一样多

思路：

第一堆只能给第二堆多干张，或者第二堆给第一堆，这取决于第一堆的初始牌量。当确定第一堆状态后，我们就不用再考虑他，第二堆就变成新的第一堆。
所以我们先求平均值（也就是最终每堆多少张），然后从第一堆开始往后一次比较，如果相等就跳过，如果不是，移动次数就加1
比如：1 1 1 9
平均值为3
第四堆多6张，全部移动到第三堆，然后第三堆再移动四张到第二堆，第二堆再移动两张到第一堆。一共三步

代码：

#include<iostream>
using namespace std;
int a[10002];
//int jozky()
//{

//}
int main()
{
    int n,ave=0,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ave=ave+a[i];
    }   
       ave=ave/n;
    for(int i=1;i<=n;i++)
    {

        a[i]=a[i]-ave;//与平均值的距离 
   }
    for(int i=1;i<=n;i++)
    {
                if(a[i] == 0)    continue;
        sum++;
        a[i+1] = a[i]+a[i+1];//a是前缀和（表示前i堆与平均值的距离情况） 

    }
    cout<<sum<<endl;
    return 0;
}

环形

P2512 [HAOI2008]糖果传递

题目描述

我们将上一个问题由线性改成环形，也就是第一位和最后一位是相邻的，他们之间也可以互相给牌，这样任意一位都有两个临点
问最少代价是多少？挪动一张牌的代价是1
（上一个题是问最少移动多少次）

思路

既然是环形，我们完全可以拆环成链，然后用上面那个题的方式来解决
在这里插入图片描述
橙色圈住的部分我们都可以看做坐标上的点，那xn的绝对值我们就可以看做点x与橙色部分的距离，然后求最短距离和
如果有偶数个点，就是最中间两个点的平均
如果是奇数，就是最中间的点
橙色部分每个点之间的距离都是有规律的，代码里有

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn=1e6+4;
ll a[maxn];
int main()
{
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sum/=n;
    for(int i=n;i>1;i--)
    {
        a[i]=sum-a[i]+a[i+1];//为啥是这个公式可以在我那个推到里面得到 
    }
    a[1]=0;
    sort(a+1,a+n+1);
    ll res=0;
    int mid=(n+1)/2;
    for(int i=1;i<=n;i++)
    {
        res+=abs(a[i]-a[mid]);
    } 
    cout<<res<<endl;
    return 0;

}