D. 小江的集合拆分

    传统题 1000ms 256MiB

小江的集合拆分

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小江又带着大家学习新定义啦!今天要学习的内容是集合的 mex,集合的 mex 指的是一个集合没有出现过的最小自然数。例如,mex({1,2}) = 0、mex({0,1,2,3}) = 4。

现在你有一个包含 n 个元素的集合,你可以将它分成任意个数量的新集合,使得所有新集合的 mex 值之和最大,求这个最大值是多少。

输入描述

第一行输入一行一个正整数 n,接下来一行包含 n 个非负整数,表示集合中的元素 a_i

输出描述

输出一行一个整数表示答案。

示例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 个测试点有

对于所有测试点,有


8.27普及

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-9-11 18:30
结束于
2024-9-11 21:00
持续时间
2.5 小时
主持人
参赛人数
22