均分纸牌有三种情况:线性,环形,二维
@[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;

}