洛谷P1031 [NOIP2002]均分纸牌

Question


分析:题意中说扑克牌总数是n的整数倍实际上就是在暗示,我们可以先把均分后每堆纸牌的数量算出来。

"...."告诉我们只能相邻两个之间操作,但一定要少的问前一个要,多的给下一个吗,不需要,因为你问

上一个要事实上也上上一个绕了一圈给你送过来的,所以我们就一堆一堆操作,多了少了都由下一堆承担,

有人说,很好吗,这不就移动n-1次吗,额,万一恰巧到哪个哪个正好是average,就不用了操作了。

 

洛谷P1031 [NOIP2002]均分纸牌
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int average,a[105],n,sum,res;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    average=sum/n;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==average) continue;
        else if(a[i]<average)
        {
            a[i+1]=a[i+1]-(average-a[i]);
            a[i]=average;
            res++;
        }
        else
        {
            a[i+1]=a[i+1]+a[i]-average;
            a[i]=average;
            res++;
        }
    }
    printf("%d",res);
    return 0;
}
View Code

 

上一篇:NOIP2002提高组题解


下一篇:1314:【例3.6】过河卒(Noip2002)