| 题目名称 | 778. [Violet 1] 木偶 |
|---|---|
| 输入输出 | puppet.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 王者自由
于2012-04-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：3， 通过率：33.33% | ||||
 一個人的雨 |
100 | 0.006 s | 0.31 MiB | C++ |
|
一個人的雨 |
0 | 0.001 s | 0.31 MiB | C++ |
 Makazeu |
0 | 0.003 s | 0.26 MiB | C++ |
| 关于 木偶 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
标程献上...话说我也不太懂...
| ||||
题目描述
Nimo是小镇上最出色的木偶剧演员。他经常带着自己的木偶们在附近的镇上演出。为了方便起见，我们给每个木偶设定一个特征值pi，每个木偶都有一个原装的提线，提线的特征值和木偶是相等的，即也为pi。当一个木偶和一个提线的特征值相差超过1 时，提线将不能组装到木偶上。现在木偶和提线被Nimo不小心全部打乱了，Nimo决定对这些木偶和提线重新配对。
他采取这样的策略：每次拿出一个木偶，再在未配对的提线里面随机抽一个可以组装到这个木偶上的提线，将它们配对，如果当前木偶没有可以配对的提线，Nimo将扔掉这个木偶。
现在他想知道的是，在最坏情况下，他最多会扔掉多少个木偶。
输入格式
测试文件中包含若干个测试点。每个测试点包含两行。第一行包含一个整数N ，表示有N 个木偶。
接下来一行N 个整数，第i 个整数pi，表示第i 个木偶及其原装提线的特征值。
输出格式
一行一个整数，表示最多可能扔掉多少个木偶。样例输入
31 2 3
8
1 2 3 3 4 2 5 4
样例输出
12
样例说明
对于样例1 ，Nimo可能会把第2 个木偶和第 1 个木偶的原配提线配对，第 3 个木偶和第2 个木偶的原配提线配对，这样第 3 个木偶就会被扔掉。
数据范围与约定
对于10% 的数据，满足 1 <= N <= 10。对于20% 的数据，满足 1 <= N <= 20。
对于100% 的数据，满足 1 <= N <= 50， 1 <= pi <= 100。