P9421题解

Yuneko · 2023-06-23 20:06:03 · 题解

这个题目，写一个桶就好了，首先，输入 a 数组，然后将 a 数组遍历一遍，将每个学生的 id 编号加入对应的 b[i] 的桶里，其次，每个 id 有 3 种情况：

最后因为是修改，所以只要将 id>2 的 id 编号移到 id<2 的 id 编号即可，只需要输出 sum/2 即可，但是，如果所有学生的 id 都是一样的话，那么由于没有 id=1 的 id ，因此没有可以直接依靠的 id，所以就要输出 sum 而不是 sum/2 ，话不多说，上代码！

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],sum;// a 数组表示每个学生的 id ，b数组表示每个 id 出现了几次，sum 表示存储需要更改的 id 数 。
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) 
    {
        cin>>a[i];
        b[a[i]]++; //将 b 的第 a[i] 项增加 1。
    }
    for(int i=0;i<=n;i++)
    {
        if(b[i]==1) //如果 b[i] 等于 1。
            sum++; //那么需要修改的次数就增加 1 次。
        if(b[i]>2) //如果 b[i] 大于 2。
            sum+=b[i]-2; //那么需要修改的次数就增加 b[i]-2 次。
    }
    for(int i=0;i<=n;i++) //注意，序号是在 n 以内，所以要小于等于。
        if(b[i]-2==sum)
        {
            cout<<sum; //如果所有学生数字都一样，那么就直接输出 sum。
            return 0;   
        }
    cout<<sum/2; //否则就输出 sum/2。
    return 0;
}