问题3125--最小糖果数

3125: 最小糖果数

时间限制: 1 Sec  内存限制: 256 MB
提交: 94  解决: 9
[状态] [讨论版] [提交] [命题人:]
题目描述
小 Y 和妹妹玩游戏,妹妹给了小 Y 一组卡牌,用一个长度为n的数组来表示这组卡牌。小 Y 和妹妹约定,每次可以移除一张卡牌,但是同时需要给妹妹买 MEX(a) 个糖果(先移除卡牌,再添加MEX(a)个糖果)
数组的 MEX (a) 即不属于数组a的最小非负整数
例如:
[2,2,1] 的 MEX 是 0,因为 0 不属于数组。
[3,1,0,1] 的 MEX 是 2,因为 0 和 1 属于数组,而2不属于数组。
[0,3,1,2] 的 MEX 是 4,因为 0、1、2 和 3 属于数组,而 4 不属于数组
现在小Y想知道,给卡牌全部移除后小Y一共要给妹妹买多少颗糖果?
输入
一个整数 n,以及各组卡牌 ai,1 <= n <= 5000 , 0 <= a< 1e9
输出
所求得最小糖果数
样例输入 Copy
8
5 2 1 0 3 0 4 0
样例输出 Copy
3
来源/分类