Problem D: *森林中的兔子
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:28
Solved:19
Description
森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你(指被提问的兔子)颜色相同?" ,将答案收集到一个整数数组 answers 中,其中 answers[i] 是第 i 只兔子的回答。
给你数组 answers ,返回森林中兔子的最少数量。
例如兔子回答的数组 answers=[ 1,1,2,0] 。经如下解析后可以得森林中兔子最少有 6 只。
解释:
两只回答了 "1" 的兔子可能有相同的颜色,设为灰色。 之后回答了 "2" 的兔子不会是灰色,否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 此外,森林中还应有另外 2 只蓝色兔子的没回答不包含在数组中。因此蓝色兔子有 3 只。
最后回答了“0” 的兔子为红色。因为它没有见到红色的兔子,就这一只红色的兔子。
因此森林中兔子的最少数量是 6 只:4 只回答的和 2 只没有回答的。
Input
输入第一行为 n个答案。第二行为answers回答数组中的 n个回答的数字,表示颜色(数字间空格分隔)。
Output
输出一个整数,为森林中兔子的最少数量。
Sample Input Copy
5
3 3 3 2 4
Sample Output Copy
12
HINT
-
1 <= n <= 3*10^5
-
0 <= answers[i] < 1000