atcoder#ARC087A. [ABC082C] Good Sequence

[ABC082C] Good Sequence

题目描述

長さ N N の正整数の列 a = (a1, a2, ..., aN) a\ =\ (a_1,\ a_2,\ ...,\ a_N) が与えられます。 あなたの目標は、a a のうちいくつかの要素を取り除き、a a 良い数列 にすることです。

ここで、数列 b b 良い数列 であるとは、次の条件が成り立つことです。

  • b b の各要素 x x について、b b に値 x x はちょうど x x 個含まれる。

例えば、(3, 3, 3) (3,\ 3,\ 3) , (4, 2, 4, 1, 4, 2, 4) (4,\ 2,\ 4,\ 1,\ 4,\ 2,\ 4) , () () (空の数列) は良い数列です。 一方、(3, 3, 3, 3) (3,\ 3,\ 3,\ 3) , (2, 4, 1, 4, 2) (2,\ 4,\ 1,\ 4,\ 2) は良い数列ではありません。

a a を良い数列にするために取り除くべき要素の個数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N a1 a_1 a2 a_2 ... ... aN a_N

输出格式

a a を良い数列にするために取り除くべき要素の個数の最小値を出力せよ。

题目大意

现在给你的长度正整数的序列,你的目标是删除某些元素,让其是一个很好的序列。

好序列是指这个序列中每个数字的个数都为这个数字

Translated by @Chthology

4
3 3 3 3
1
5
2 4 1 4 2
2
6
1 2 2 3 3 3
0
1
1000000000
1
8
2 7 1 8 2 8 1 8
5

提示

制約

  • 1  N  105 1\ \leq\ N\ \leq\ 10^5
  • ai a_i は整数である。
  • 1  ai  109 1\ \leq\ a_i\ \leq\ 10^9

Sample Explanation 1

例えば、要素 3 3 1 1 個取り除くと、(3, 3, 3) (3,\ 3,\ 3) は良い数列になります。

Sample Explanation 2

例えば、要素 4 4 2 2 個取り除くと、(2, 1, 2) (2,\ 1,\ 2) は良い数列になります。

Sample Explanation 4

要素 109 10^9 1 1 個取り除くと、() () は良い数列になります。