#5613. 决斗
-
ID: 5613
Type: Default
1000ms
128MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
决斗
说明
今天是小Q的生日，他得到了n张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第i张卡代表一只攻击力为$r _ { i } ,$防御力也为$r _ { i }$的怪兽。 一场游戏分为若干回合。每回合，小Q会选择某只怪兽i以及另一只怪兽j(i≠j)并让怪兽i向怪兽j发起攻击。此时，若怪兽i的攻击力小于等于怪兽j的防御力，则无事发生；否则，怪兽j的防御被打破，怪兽j退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束 小Q希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。输入格式
从文件duel.in中读入数据。 输入的第一行包含一个正整数n，表示卡牌的个数。 输入的第二行包含n个正整数，其中第i个正整数表示第i个怪兽的攻击力及防御力$r _ { i } 。$输出格式
输出到文件 duel.out中。
输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。
5
1 2 3 1 22
提示
【样例 1 解释】
其中一种最优方案为：第一回合让第 2 只怪兽向第 1 只怪兽发起攻击，第二回合
让第 5 只怪兽向第 4 只怪兽发起攻击，第三回合让第 3 只怪兽向第 5 只怪兽发起攻击。
此时没有退出游戏的怪兽都进行过攻击，游戏结束。可以证明没有更优的攻击顺序
【样例 2 输入】
10
136 136 136 2417 136 136 2417 136 136 136
【样例 2 输出】
8
【样例 3】
见选手目录下的 duel/duel3.in 与 duel/duel3.ans。
该样例满足 ∀1 ≤ i ≤ n, ri ≤ 2。
【样例 4】
见选手目录下的 duel/duel4.in 与 duel/duel4.ans。
## 【数据范围】
对于所有测试数据，保证： $1 \leq n \leq 1 0 ^ { 5 } ,$ $1 \leq r _ { i } \leq 1 0 ^ { 5 }$
| 测试点 | n | $r _ { i }$ | 特殊性质 |
| -- | -- | -- | -- |
| $1 \sim$A | $\leq$10 | $\leq 1 0 ^ { 5 }$ | 无特殊性质 |
| $5 \sim$10 | $\leq 1 0 ^ { 5 }$ | $\leq 2$ | 无特殊性质 |
| 11\~15 | $\leq 3 0$ | $\leq 1 0 ^ { 5 }$ | 特殊性质A |
| $1 6 \sim 2 0$ | $\leq 1 0 ^ { 5 }$ | $\leq 1 0 ^ { 5 }$ | 无特殊性质 |
特殊性质A：保证每个$r _ { i }$在可能的值域中独立均匀随机生成。