小江的集合拆分
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小江又带着大家学习新定义啦!今天要学习的内容是集合的 mex,集合的 mex 指的是一个集合没有出现过的最小自然数。例如,mex({1,2}) = 0、mex({0,1,2,3}) = 4。
现在你有一个包含 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 mex 值之和最大,求这个最大值是多少。
输入描述
第一行输入一行一个正整数 ,接下来一行包含 个非负整数,表示集合中的元素
输出描述
输出一行一个整数表示答案。
示例1
5
0 0 1 1 2
5
分成两个集合 {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
0
因为原集合没有 0,所以无论怎么分集合,每一个新集合都不会有 0,所以每一个集合的 mex 都为 0,答案一定为 0.
输入输出备注
本题共有 10 个测试点
第一个测试点有
第二个测试点有
第 3-4 个测试点有
对于所有测试点,有