均分纸牌有三种情况：线性，环形，二维
线性
题目描述
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;
}
环形
题目描述
我们将上一个问题由线性改成环形，也就是第一位和最后一位是相邻的，他们之间也可以互相给牌，这样任意一位都有两个临点
问最少代价是多少？挪动一张牌的代价是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;
}
京公网安备 11010502036488号