题解：P9421 [蓝桥杯 2023 国 B] 班级活动

lailai0916 · 2023-06-23 21:44:43 · 题解

题意简述

每次修改 1 个元素，求序列中恰好每 2 个元素相同的最小操作次数。

解题思路

对于每个元素 i 的出现次数 a_i，分类讨论：

1. 如果 a_i=2，显然无需修改。
2. 如果 a_i=1，可以直接修改其他元素，也可以把其他元素修改为 i。
3. 如果 a_i>2，修改多余的 a_i-2 个元素，且优先修改为其他 a_j=1 的元素。

具体实现：读入 t，记录每个数出现的次数 a_i，枚举所有的 a_i：

对于 s_1 和 s_2，分类讨论：

1. 如果 s_2\ge s_1，说明有足够 a_i>2 的元素可以给 a_i=1 的元素；
2. 否则，还要修改 s1-s2 个 a_i=1 的元素，每 2 个一组，要修改 \frac{s1-s2}{2} 个元素。

综上，最终答案为：

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        a[t]++;
    }
    int s1=0,s2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==1)s1+=1;
        else if(a[i]>2)s2+=a[i]-2;
    }
    cout<<s2+max(s1-s2,0)/2<<'\n';
    return 0;
}