题目描述
【题目描述】
鸡尾酒又带着大家学习新定义啦!今天要学习的内容是集合的 mex,集合的 mex 指的是一个集合没有出现过的最小自然数。
例如,mex({1,2}) = 0、mex({0,1,2,3}) = 4。
现在你有一个包含 n 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 mex 值之和最大,求这个最大值是多少。
【输入格式】
第一行输入一行一个正整数 n,接下来一行包含 n 个非负整数,表示集合中的元素 ai。
【输出格式】
输出一行一个整数表示答案。
【样例】
样例输入1
5
0 0 1 1 2
样例输出1
5
样例说明1
分成两个集合 {0, 1}, {0, 1, 2},第一个集合的 mex 为 2,第二个集合的 mex 为 3 ,两个集合的 mex 之和为 5 ,这样分集合是最大的。
当然也可以分成 {0}, {0}, {1}, {1}, {2},但是这样五个集合的 mex 之和为1 + 1 + 0 + 0 + 0 = 2。
样例输入2
5
1 2 3 4 5
样例输出2
0
样例说明2
因为原集合没有 0,所以无论怎么分集合,每一个新集合都不会有 0,所以每一 个集合的 mex 都为 0,答案一定为 0。
【数据范围】
本题共有 10 个测试点 第一个测试点有 0 < ai 第二个测试点有 ai = 0
第 3 − 4 个测试点有 0 ≤ ai ≤ 1
对于所有测试点,有 1 ≤ n ≤ 105, 0 ≤ ai ≤ 1000
题目大意
给定一个包含 \(n\) 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 \(mex\) 值之和最大,求这个最大值是多少。
关于 \(mex\) 值的定义:一个集合中没有出现过的最小自然数。
思路
该题主要考察:贪心。
众所周知,集合内是没有相同元素的。因此可以将每个分割后的新集合分类讨论:
- 集合中有 \(0\):此时需要计算集合的 \(mex\) 值。
- 集合中没有 \(0\):此时集合的 \(mex\) 值为 \(0\)。
所以,对于每一个 \(0\) 就会有对应的一个新集合。
然后,由于题目要求所有新集合的最大的 \(mex\) 值之和,所以每个新集合都要尽量有更多的元素。
但是,考虑特殊情况:对于集合 \(\{0, 1, 2, ..., 999, 1000\}\) 来说,其 \(mex\) 值为 1001。
所以要判定特殊情况。
那么,题目就迎刃而解了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int n, a[N];
int t[N];
int main()
{
scanf("%d", &n);
int cnt = 0; // cnt 用于 统计新集合个数
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
if (a[i] == 0) cnt ++ ; // 对于每一个 0 就会有对应的一个新集合
else t[a[i]] ++ ;
}
int ans = 0;
while (cnt -- ) // 依次处理每个新集合
{
// 注意 i <= 1001,应对集合为 {0, 1, 2, ..., 1000} 的情况
for (int i = 1; i <= 1001; i ++ )
{
if (t[i]) t[i] -- ;
else
{
ans += i;
break;
}
}
}
printf("%d\n", ans);
return 0;
}
标签:测试点,int,题解,样例,ai,拆分,集合,mex
From: https://www.cnblogs.com/T-hong/p/18389414