#P1630. 拆分(t2)
拆分(t2)
【题目描述】
鸡尾酒又带着大家学习新定义啦!今天要学习的内容是集合的𝑚ex,集合的mex 指的是一个集合没有出现过的最小自然数。例如,𝑚ex({1,2}) =0、mex({0,1,2,3}) = 4。
现在你有一个包含𝑛 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的mex 值之和最大,求这个最大值是多少。
【输入格式】
第一行输入一行一个正整数𝑛,接下来一行包含𝑛 个非负整数,表示集合中的元素 𝑎𝑖。
【输出格式】
输出一行一个整数表示答案。
【样例 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 < 𝑎𝑖
第二个测试点有𝑎𝑖 = 0
第 3 − 4 个测试点有 0 ≤𝑎𝑖 ≤ 1
对于所有测试点,有 1 ≤𝑛 ≤ 10^5, 0 ≤ 𝑎𝑖 ≤ 1000
相关
在下列比赛中: