问题 5329 --拆分

5329: 拆分★★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 29  解决: 17
[提交][状态][命题人:]

题目描述

鸡尾酒又带着大家学习新定义啦！今天要学习的内容是集合的 mex ，集合的 mex 指的是一个集合没有出现过的最小自然数。例如，mex({1,2}) = 0、mex({0,1,2,3}) = 4。 现在你有一个包含 n 个元素的集合，你可以将它分成任意个数量的新集合，使得所有新集合的  mex  值之和最大，求这个最大值是多少。

输入

第一行输入一行一个正整数  n ，接下来一行包含 n 个非负整数，表示集合中的 元素  a[i]。

输出

输出一行一个整数表示答案。
样例输入
Copy
【样例 1 输入】
5
0 0 1 1 2
【样例 2 输入】
5
1 2 3 4 5
样例输出
Copy
【样例 1 输出】
5
【样例 2 输入】
0

提示

【样例 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 说明】 

因为原集合没有 0，所以无论怎么分集合，每一个新集合都不会有 0，所以每一 个集合的 mex 都为 0，答案一定为 0。

第一个测试点有 0 < a[i];

 第二个测试点有 a[i] = 0 ;

第 3 − 4 个测试点有 0 ≤ a[i] ≤ 1 ;

对于所有测试点，有 1 ≤a[i]<=1000

来源

模拟赛第一场问题B 

[提交][状态]