P11231 [CSP-S 2024] 决斗
Tag：模拟、双指针、排序
题目描述
今天是小 Q 的生日，他得到了 \(n\) 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 \(i\) 张卡代表一只攻击力为 \(r_i\)，防御力也为 \(r_i\) 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 \(i\) 以及另一只怪兽 \(j(i \neq j)\)，并让怪兽 \(i\) 向怪兽 \(j\) 发起攻击。此时，若怪兽 \(i\) 的攻击力小于等于怪兽 \(j\) 的防御力，则无事发生；否则，怪兽 \(j\) 的防御被打破，怪兽 \(j\) 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。
数据说明： \(n \leq 10^5, r_i \leq 10^5\)
分析
首先要注意到题目中提及的一只怪兽最多只能发起一次攻击， 因此我们首先应该考虑的就是尽可能利用所有怪兽的价值， 也就是说我们要尽可能多地让怪兽进行攻击。
因为只有当某只怪兽的数值大于另一只时，才能成功击败怪兽。 因此我们将所有怪兽的能力值进行排序， 之后我们可以维护一个双指针状物， 每次我们都让一个怪兽试图攻击一个剩余怪兽中能力值最小的， 直到无法有怪兽能够做出有效攻击即可。
代码实现
void NeverSayNever() {
int n; cin >> n;
vector<int> vec(n);
for (auto &x: vec) cin >> x;
int l = 0;
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i++) {
if (vec[i] <= vec[l]) continue;
l++;
}
cout << n - l << endl;
}
日志
本页面创建于 2024/03/14 15:57