洛谷P14130题解

分析

题意

给你一个非负整数序列，你需要把它拆成尽可能多的子序列。要求有三点：

1. 每个子序列都必须有 $0$。

2. 同一个数字，不能出现在两个不同的子序列里。

3. 每个子序列的 $\text{mex}$ 值不能是 $0$。

思路

因为每个子序列都必须有一个 $0$，所以 $k$ 最大就只能是原序列里 $0$ 的总个数。

非零数字是不会限制 $k$ 的，因为我们可以把所有相同的非零数字打包成一个“块”，然后把这些“块” 随意地分配给我们创建的 $k$ 个子序列。只要每个子序列都有一个 $0$，它就是合法的。

所以，答案就是原序列中 $0$ 的个数。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int cnt0 = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (a == 0) cnt0++;
    }
    cout << cnt0;
    return 0;
}