📝 题目大意

给定一个长度为 $N$ 的正整数序列，可以删除任意元素。目标是使序列变为"好数列"——即对于序列中每个值 $x$，恰好出现 $x$ 次。求最少删除元素个数。

💡 解题思路

1. 题目分析：不同数值之间是相互独立的——保留某个值为 $v$ 的元素不会影响其他值的合法性。因此可以逐个数值单独决策。数据范围 $a_i \leq 10^9$ 很大，需要用 map 统计频率。

2. 算法推导：

   • 首先统计每个数值的出现次数（频率），用 map<long long, int> 存储。
   • 对于数值 $v$，设其出现次数为 $cnt$：
     • 若 $cnt \geq v$：我们可以保留恰好 $v$ 个元素，使其成为合法的"好数列"组。多余 $cnt - v$ 个必须删除。
     • 若 $cnt < v$：即使全部保留也无法满足"恰好 $v$ 个"的条件，因此必须全部删除（$cnt$ 个全部丢弃）。
   • 核心贪心策略：对每个数值 $v$，能保留则保留 $v$ 个，不能保留则全部删除。由于各数值独立，贪心选择就是全局最优。
   • 最终答案 = 总元素数 $N$ 减去保留的总数 $keep$。

3. 边界与细节：

   • 空数列 $()$ 也是好数列，因此答案总是合法的——最坏情况全删，答案为 $N$。
   • $a_i$ 最大可达 $10^9$，必须用 long long 存储键值，否则会溢出。
   • 当 $cnt = v$ 时恰好保留全部，不增不减；当 $cnt > v$ 时保留 $v$ 个；当 $cnt < v$ 时全部删除。
   • 样例 4：$N=1$，$a_1=10^9$，$cnt=1 < 10^9$，全部删除，答案为 $1$。

⏱️ 复杂度分析

• 时间复杂度：统计频率需遍历 $N$ 个元素，每次 map 插入/查询为 $O(\log N)$，总计 $O(N \log N)$。遍历 map 中所有不同数值也是 $O(N)$。
• 空间复杂度：map 最多存储 $N$ 个不同键值对，为 $O(N)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    map<long long, int> freq;          // 统计每个数值的出现次数，键用 long long 防止溢出
    for (int i = 0; i < N; ++i) {
        long long x;
        cin >> x;
        ++freq[x];                     // 计数
    }
    long long keep = 0;                // 可以保留的元素总数
    for (const auto& p : freq) {
        long long v = p.first;         // 当前数值
        int cnt = p.second;            // 该数值的出现次数
        if (cnt >= v) {                // 若数量足够，保留恰好 v 个
            keep += v;                 // 保留 v 个，多余的 cnt - v 个将被删除
        }
        // 若 cnt < v，则无法满足条件，全部删除（keep 不增加）
    }
    cout << N - keep << endl;          // 删除数 = 总数 - 保留数
    return 0;
}