P1031 [NOIP2002 提高组] 均分纸牌

Hypnotize · 2021-06-05 15:50:28 · 个人记录

这道题的重点就是平均数，既然最后是使得所有的牌堆牌数相同，那为什么不以最后的牌数作为基准，来移动每一堆牌呢？

即：计算每一堆牌与平均数的差值，若结果不为0则移动。

上代码（里面有详尽的注释）：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10005];
int x=0;
int ans=0;
int l,r; 
inline int read(){
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        c=(c<<1)+(c<<3)+(ch^48);
        ch=getchar();
    }
    return c*f;
}//一个不那么寻常的快读 
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        x+=a[i];
    }
    x/=n;//先把平均数算出来 
    for(int i=1;i<=n;i++){
        a[i]-=x;
    }//计算差值 
    int i=1;
    while(a[i]==0) i++;
    l=i;
    int j=n;
    while(a[j]==0) j--;
    r=j;//左右两边是0的话就不用算了！
    for(int i=l;i<=r;i++){
        if(a[i]!=0){
            a[i+1]+=a[i];
            a[i]=0;
            ans++;
        }//如果此堆牌与平均数不同则移动，答案加一 
        else continue;//如果移动就不用管了 
    }
    printf("%d",ans);//输出答案 
    return 0;//华丽的结束 
}