QOJ.ac

QOJ

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓

#15711. 地牢平衡

Estadísticas

你正在开发一款新的 RPG 游戏,其中每种怪物都有一个特殊的规则,规定它在一个关卡中应该出现的次数。

一个关卡由一个整数数组 $a_1, a_2, \dots, a_n$ 表示,其中每个整数代表一个怪物的类型。

如果对于出现的每种怪物类型 $x$,该关卡中恰好有 $x$ 个该类型的怪物,则该关卡被认为是平衡的。例如,一个平衡的关卡可能包含三个类型为 3 的怪物、五个类型为 5 的怪物,依此类推。一个空关卡(完全没有怪物)也被认为是平衡的。

不幸的是,你当前的关卡设计不一定是平衡的。你可以删除一些怪物(即从数组中移除元素)来使其达到平衡。

给定数组 $a_1, a_2, \dots, a_n$,求使关卡达到平衡所需移除的最少怪物数量。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$) —— 关卡中当前的怪物数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) —— 怪物的类型。

输出格式

输出单行,包含一个整数:为使关卡达到平衡,你需要从关卡中移除的最少怪物数量。

样例

输入 1

5
1 1 2 2 3

输出 1

2

输入 2

10
1 2 3 2 4 4 4 4 5 2

输出 2

3

说明

样例 1 说明:在第一个样例中,你可以移除一个类型为 1 的怪物和一个类型为 3 的怪物。关卡随后变为 [1, 2, 2],这是平衡的(它包含一个类型为 1 的怪物和两个类型为 2 的怪物)。你无法通过少于 2 次移除使关卡达到平衡,因此答案为 2。

样例 2 说明:在第二个样例中,你可以将关卡变为 [1, 2, 4, 4, 4, 4, 2]。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.