题目描述
今天是小 Q 的生日,他得到了 \(n\) 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”,其中,第 \(i\) 张卡代表一只攻击力为 \(r_i\),防御力也为 \(r_i\) 的怪兽。
一场游戏分为若干回合。每回合,小 Q 会选择某只怪兽 \(i\) 以及另一只怪兽 \(j(i \neq j)\),并让怪兽 \(i\) 向怪兽 \(j\) 发起攻击。此时,若怪兽 \(i\) 的攻击力小于等于怪兽 \(j\) 的防御力,则无事发生;否则,怪兽 \(j\) 的防御被打破,怪兽 \(j\) 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时,游戏结束。
小 Q 希望决定一组攻击顺序,使得在游戏结束时,未退出游戏的怪兽数量尽可能少。
对于所有测试数据,保证:\(1 \leq n \leq 10^5\),\(1 \leq r_i \leq 10^5\)。
solution
可以优先将 \(r_i\) 小的怪物淘汰出局,也可以优先使用 \(r_i\) 小的怪物的攻击。对 \(r_i\) 排序后从小到大维护两个指针 \(i, j\),表示当前将要用 \(r_j\) 淘汰 \(r_i\),始终保持 \(r_j>r_i, j\leq n\),每次发动一次攻击后 \(i, j\) 都右移。复杂度 \(O(n\log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define endl "\n"
#endif
using LL = long long;
int n, a[100010];
int main() {
#ifndef LOCAL
#ifdef NF
freopen("duel.in", "r", stdin);
freopen("duel.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 1, j = 2; max(i, j) <= n; i++) {
while (j <= n && a[j] <= a[i]) ++j;
if (j <= n) ++ans, ++j;
}
cout << n - ans << endl;
return 0;
}
标签:怪兽,游戏,int,题解,P11231,2024,leq,攻击,define
From: https://www.cnblogs.com/caijianhong/p/18526008/solution-P11231