P9421题解

LiJoQiao · 2023-06-24 08:32:05 · 题解

题目链接 评测记录
读题知，有 n 个小朋友，需要将落单的小朋友和 id 已经有两人使用的小朋友（后文简称 id 溢出的小朋友）的 id 修改，使得每个小朋友使用的 id 只有两个人使用。
更抽象点，就是 n 个数需要修改后每个数有且只有一个数与其相等，输出修改次数。

进行分类讨论。

• 如果有两个小朋友的 id 已经满足相等且没有其他小朋友的 id 与其相等的话，我们只需跳过不用修改。

• >1.其他小朋友修改与其配对。 >2.该小朋友进行修改，与其他小朋友配对。

因为 id 溢出的小朋友必须修改，我们先让该小朋友的 id 与落单的小朋友配对，然后又有三种情况。

• 配对后无落单的小朋友，也无 id 溢出的小朋友，无需多加修改。

• 配对后只剩下落单的小朋友，此时每两个小朋友只需其中一个小朋友修改使得两个小朋友配对即可。

• 配对后只剩下 id 溢出的小朋友，因为这两个小朋友的 id 必须修改使得与原 id 不同，所以输出结果直接加上 id 溢出的小朋友的数量即可。

经过上述操作后，每个小朋友有且只有一个小朋友的 id 与其 id 相等。进行输出结果。

代码如下。

#include<iostream>
using namespace std;
const int MAXN=100010;
int bucket[MAXN],ans,oneid,outid;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//一串优化
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)//输入n个小朋友的id
    {
        int temp;
        cin>>temp;
        if(bucket[temp]==0)
        {
            bucket[temp]++;
            oneid++;//落单的小朋友
        }
        else if(bucket[temp]==1)
        {
            bucket[temp]++;
            oneid--;//此时有一位小朋友id与某位小朋友相同，原本落单的小朋友-1
        }
        else
        {
            outid++;//这个小朋友的id已经有两个人用了，该小朋友只能修改自己的id
        }
    }
    //先让id溢出的小朋友与落单的小朋友id相同
    int pd=min(oneid,outid);//分两种情况，一种是落单的多，一种是id溢出的多，取其中最小值得到落单和id溢出配对的数量
    ans+=pd;//配对时只需id被用过的小朋友修改
    oneid-=pd;//配对后落单小朋友数量减少
    outid-=pd;//配对后id溢出的小朋友数量减少
    //剩下的两种情况
    if(oneid)//只剩下落单的
    {
        ans+=oneid/2;//落单的小朋友只有一个修改即可
        //oneid=0;//此处不必写入这句代码，只是为了方便读者理解
        //两个落单的小朋友修改后数量为0，修改结束
    }
    if(outid)//只剩下id溢出的小朋友
    {
        ans+=outid;//由于都是溢出的小朋友，都需要修改
        //outid=0;//此处不必写入这句代码，只是为了方便读者理解
        //id溢出的小朋友修改后数量为0，修改结束
    }
    cout<<ans;
    return 0;
}