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

· · 题解

思路

先把每个 id 的人数统计好，然后 id 的数量有两种情况：

把 id 大于等于二的学生数减二用 sum1 累加，id 小于二的学生数用 sum2 累加。

如果 sum1>sum2，则只要把 id 相同且人数大于等于二的人的 id 改掉即可，即输出 sum1。

如果 sum1 \le sum2，则把 id 相同的人改掉后剩下的不符合题意，应把一半 id 人数为一的改掉。即输出 sum1+\dfrac{sum2-sum1}{2}。

代码

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

const int N = 1e6 + 10;
typedef long long ll;

int a[N], cnt[N];
int n;
int sum1 = 0, sum2 = 0;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (int i = 1; i <= 1e6; i++) {
        if (cnt[i] >= 2) {
            sum1 += (cnt[i] - 2);
        } else {
            sum2 += cnt[i];
        }
    }
    if (sum1 > sum2) {
        cout << sum1 << "\n";
    } else {
        cout << sum1 + (sum2 - sum1) / 2 << "\n";
    }
    return 0;
}