NOIP 2002 均分纸牌(贪心||模拟)

我不是女神ヾ 2022-05-17 12:25 434阅读 0赞

题目描述

有N堆纸牌，编号分别为1，2，...，N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。  
移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。  
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。  
例如N=4，4堆纸牌数分别为：  
  ① 9 ② 8 ③ 17 ④ 6  
移动3次可达到目的：  
  从③取4张牌放到④（9 8 13 10）->从③取3张牌放到②（9 11 10 10）->从②取1张牌放到①（10 10 10 10）。

输入

每个测试文件只包含一组测试数据，每组输入的第一行输入一个整数N（1<=N<=100），表示有N堆纸牌。  
接下来一行输入N个整数A1 A2...An，表示每堆纸牌初始数，1<=Ai<=10000。

输出

对于每组输入数据，输出所有堆均达到相等时的最少移动次数。

分析：n堆的纸牌最多移动n-1次就可以使每堆纸牌被均分。用贪心的思想，先预处理出每堆纸牌和平均数的差值，然后从左往右把这些值加起来（可以视为将这些纸牌不断放在一起），如果下一堆纸牌加上前面的已经为0了，就说明这堆纸牌不用再进行操作，（可以视为它和它前面的堆已经被均分了），否则的话，就让次数，如果累加到一堆的时候不为0，就让次数+1。其实这可以看做是一个模拟移动纸牌的过程。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e2+7;
    const int inf=0x3f3f3f3f;
    int a[maxn];
    
    int main()
    {
        int N,sum=0;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        int ave=sum/N;
        for(int i=0;i<N;i++)
        {
            a[i]-=ave;
        }
        int ans=0;
        for(int i=0;i<N;i++)
        {
            if(a[i]==0) continue;
            a[i+1]+=a[i];
            ans++;
        }
        printf("%d\n",ans);
        return 0;
    }

在网上看到一个大神用的模拟做，%%%。

思路是：  
1. 先求出前缀和（求出前i堆纸牌的总和），并求出每堆纸牌的平均值。

2. 然后从左到右，根据当前的前i堆的和sum(i)，与前i堆的期望和（即i\*ave），进行比较，如果多了，则向后面移动一次纸牌（更新a\[i\], sum\[i\], a\[i+1\]）。一轮过后，使得每堆无需再向后调整(有点类似快排的思想，一个区域内的部分达到稳定）。

3. 再从右向左，根据每堆的纸牌数a\[i\]，与每堆期望纸牌数ave比较，如果多了，则向前移动纸牌（更新a\[i\], sum\[i-1\], a\[i-1\]）  
其实也可以不更新sum了。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e2+7;
    int a[maxn];
    int sum[maxn];
    
    int main()
    {
        int N;
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        int ave=sum[N]/N;
        int ans=0;
        for(int i=1;i<=N;i++)
        {
            if(sum[i]>i*ave){
                int d=sum[i]-i*ave;
                sum[i]-=d;//可以不更新sum数组了，因为前i堆的不会再用了
                a[i+1]+=d;
                a[i]-=d;
                ans++;
            }
        }
        for(int i=N;i>=1;i--)
        {
            if(a[i]>ave){
                int d=a[i]-ave;
                a[i-1]+=d;
                a[i]-=d;
                sum[i-1]+=d;//这里也可以不再更新了，因为是用的每堆的牌数和ave进行比较
                ans++;
            }
        }
        printf("%d\n",ans);
        return 0;
    }