P1731. [NOIP2002 提高组] 均分纸牌 题解

题面传送门

涉及算法：贪心，模拟

第一步，看题，有题目可知，纸牌的总数一定是$N$的倍数，那这一条件就为我们后面的贪心奠定了基础。

第二步，想思路，如果就参照普通的思路将比平均值多的移到少的上面，那显然这不是最少需要的步骤，就拿样例举例：

输入样例：9 8 17 6

这组样例的平均值是：10，$A_1$缺了1，$A_2$缺了3，$A_3$多了7，$A_4$少了4

如果按照我们原来的把多的移到少的上去的思路，那么把$A_1$缺了的1补上就要从$A_3$上移1到这上面，这样就需要2步，再从$A_3$上移2到$A_2$上，这样有需要1步，同理，从$A_3$移4到$A_4$上，又需要1步

总的步数是：$2 + 1 + 1 = 4$，显然，这与样例不符，那要如何做呢？

而我们的贪心策略，也就根据普通做法而产生了

如果我们把所有的数都减去平均值，那么整个样例就会变成：-1 -2 7 -4，不难发现，负数表示当前纸牌缺了多少，正数表示当前纸牌多了多少，那么我们只需要让所有数都向0靠拢，也就是我们修改后的样例全部向右移动

这样的操作进行一次样例将变成：0 -3 7 -4，第二次：0 0 4 -4，第三次：0 0 0 0，这样算下来就是三步

第三步，代码实现：

1、算平均值：

• 这个操作很简单，只需要边输入边求和，最后再把求和的结果除以纸牌的$N$就可以

2、贪心的实现

• 这个操作的做一下预处理（我喜欢这么叫，具体是不是，得看大家怎么认为），预处理怎么做呢？其实就是思路中的所有的数据都减去平均值
• 接下来就是真正的贪心了，如果$A_i==0$，那直接跳过，说明这里的纸牌已经不用修改了，否则就让$A_{i+1}$加上$A_i$，这样的加就相当与一次移动了，所以有关总的移动次数就要+1

3、输出答案

• 这没什么好讲的吧，也就是输出对应的移动次数而已

讲解就到这了，下面上对标的程序

对标代码实现1的代码（标程①）：

// 计算平均值
for (re i = 1; i <= n; i++)
{
    cin >> a[i];
    sum += a[i];  // 累加求和
}
avg = sum / n; // avg就是酸的的平均值

对标代码实现2的代码（标程②）：

for (re i = 1; i <= n; i++)
    a[i] -= avg;  // 减去平均值，思路中有详细介绍其作用
// 下面是贪心
for (re i = 1; i < n; i++)
{
    if (a[i] == 0)
        continue;  // 如果a[i]是0，那不用做任何改动，直接跳过即可，不用计入总的步数
    a[i + 1] += a[i];  // 向右靠拢
    a[i] = 0;  // 将当前的纸牌赋值为0，应为当前纸牌缺少的或是多出的已经移到了下一张纸牌上了
    ans++;  // 将需要的步数的计数器加1，表示需要移一步
}

对标代码实现3的代码（标程③）：

cout << ans << endl;  // 输出答案

$AC~Code$

#include <bits/stdc++.h>
#define ll long long
#define re register int
using namespace std;
ll n, a[105], avg, sum, ans; // n表示纸牌总数，a表示纸牌，avg表示平均值，sum表示总和，ans表示一共需要的移动次数
int main()
{
    ios::sync_with_stdio(false); // 读入加速
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    /*
    这里我就不放代码了，只要把标程全部复制下来就可以了
    */
    return 0;
}

算了，还是上完整代码吧！

$AC~Code$

#include <bits/stdc++.h>
#define ll long long
#define re register int
using namespace std;
ll n, a[105], avg, sum, ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (re i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    avg = sum / n;
    for (re i = 1; i <= n; i++)
        a[i] -= avg;
    for (re i = 1; i < n; i++)
    {
        if (a[i] == 0)
            continue;
        a[i + 1] += a[i];
        a[i] = 0;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

代码很短吧，说起来麻烦，其实做起来很简单

End，撒花~~~

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int avg=0, n, a[101], i, tot=0, j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        avg+=a[i];
    }
    avg/=i;
    for(j=0;j<n;j++) a[j]-=avg;
    i=0;j=n-1;
    while(a[i]==0&&i<n) i++;
    while(a[j]==0&&j>1) j--;
    for(int t=i;t<j;t++)
    {  
        if(a[t]==0) continue;
        a[t+1]+=a[t];
        a[t]=0;
        tot++;
    }
    cout<<tot;
    return 0;
}