[CSP-S 2024] 决斗
题目描述
今天是小 Q 的生日，他得到了 n n n 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 i i i 张卡代表一只攻击力为 r i r_i ri，防御力也为 r i r_i ri 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 i i i 以及另一只怪兽 j ( i ≠ j ) j(i \neq j) j(i=j)，并让怪兽 i i i 向怪兽 j j j 发起攻击。此时，若怪兽 i i i 的攻击力小于等于怪兽 j j j 的防御力，则无事发生；否则，怪兽 j j j 的防御被打破，怪兽 j j j 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。
输入格式
输入的第一行包含一个正整数 n n n，表示卡牌的个数。
输入的第二行包含 n n n 个正整数，其中第 i i i 个正整数表示第 i i i 个怪兽的攻击力及防御力 r i r_i ri。
输出格式
输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。
样例 #1
样例输入 #1
5
1 2 3 1 2
样例输出 #1
2
样例 #2
样例输入 #2
10
136 136 136 2417 136 136 2417 136 136 136
样例输出 #2
8
提示
【样例 1 解释】
其中一种最优方案为：第一回合让第 2 2 2 只怪兽向第 1 1 1 只怪兽发起攻击，第二回合让第 5 5 5 只怪兽向第 4 4 4 只怪兽发起攻击，第三回合让第 3 3 3 只怪兽向第 5 5 5 只怪兽发起攻击。此时没有退出游戏的怪兽都进行过攻击，游戏结束。可以证明没有更优的攻击顺序。
【样例 3】
见选手目录下的 duel/duel3.in 与 duel/duel3.ans。
该样例满足 ∀ 1 ≤ i ≤ n , r i ≤ 2 \forall 1 \leq i \leq n, r_i \leq 2 ∀1≤i≤n,ri≤2。
【样例 4】
见选手目录下的 duel/duel4.in 与 duel/duel4.ans。
【数据范围】
对于所有测试数据，保证： 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 1 ≤ r i ≤ 1 0 5 1 \leq r_i \leq 10^5 1≤ri≤105。
| 测试点 | n n n | r i r_i ri | 特殊性质 |
|---|---|---|---|
| 1 ∼ 4 1\sim 4 1∼4 | ≤ 10 \leq 10 ≤10 | ≤ 1 0 5 \leq 10^5 ≤105 | 无特殊性质 |
| 5 ∼ 10 5\sim 10 5∼10 | ≤ 1 0 5 \leq 10^5 ≤105 | ≤ 2 \leq 2 ≤2 | 无特殊性质 |
| 11 ∼ 15 11\sim 15 11∼15 | ≤ 30 \leq 30 ≤30 | ≤ 1 0 5 \leq 10^5 ≤105 | 特殊性质 A |
| 16 ∼ 20 16\sim 20 16∼20 | ≤ 1 0 5 \leq 10^5 ≤105 | ≤ 1 0 5 \leq 10^5 ≤105 | 无特殊性质 |
特殊性质 A：保证每个 r i r_i ri 在可能的值域中独立均匀随机生成。
【解析】
此题要求剩下的怪兽最少，那么就尽量消灭更多的怪兽，所以我们可以先将怪兽按攻击防御力由小到大排序，枚举每个怪兽，找到攻击力最小可以消灭他的怪兽消灭他，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);//由小到大排序
int ans = n;//初始化怪兽数量
int p = 1;//未攻击怪兽指针
for(int i = 1; i <= n; i++) {//枚举每个怪兽
while (p <= n && a[p] <= a[i]) {//找到第一个可以消灭它的怪兽
p++;
}
if (p <= n) {//若找到了
ans--;//消灭一个怪兽
p++;//该怪兽攻击过了，换下一个
}
if (p > n) {//若找不到
break;//退出循环
}
}
cout << ans;
return 0;
}