把有效攻击看成强牌匹配弱牌，排序后用双指针求最多能击败多少只怪兽。
OJ: luogu
题目 ID: P11231
难度:普及-
标签:贪心排序
创建: 2026-06-22 18:23
更新: 2026-10-07 10:45
题意
有 n 只怪兽，第 i 只怪兽的攻击力和防御力都等于 r_i。
每回合可以选择一只还在场的怪兽 i，让它攻击另一只还在场的怪兽 j。如果 r_i > r_j，则 j 退出游戏；否则无事发生。每只怪兽整场游戏中至多发起一次攻击。
要求安排攻击顺序，使最后剩余怪兽数量最少。
思路
先看一个小数据暴力：用 alive 记录还活着的怪兽，用 used 记录已经攻击过的怪兽，递归枚举下一次攻击的攻击者和目标。
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-01 22:49
* update_at: 2026-10-01 22:49
*/
// brute.cpp：小数据搜索所有攻击顺序，用来帮助理解题意并辅助对拍。
// 状态压缩：alive 表示哪些怪兽还在场上，used 表示哪些怪兽已发起过攻击。
// 只适合 n ≤ 10 的对拍场景。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 12;
ll n;
int r[MAXN];
map<ll, int> memo; // 记忆化：(alive, used) -> 最少剩余怪兽数
// 统计二进制中 1 的个数（n ≤ 12，直接数）。
int count_bits(int x) {
int cnt = 0;
while (x > 0) {
cnt += x & 1;
x >>= 1;
}
return cnt;
}
// dfs(alive, used)：返回在当前状态下游戏结束时最少剩余怪兽数。
int dfs(int alive, int used) {
ll key = ((ll)alive << n) | used;
auto it = memo.find(key);
if (it != memo.end()) {
return it->second;
}
// 判断是否还有怪兽可以发起攻击（在场且未攻击过）。
int can_attack = 0;
for (int i = 0; i < n; i++) {
if ((alive & (1 << i)) && !(used & (1 << i))) {
can_attack = 1;
}
}
if (!can_attack) {
int ret = count_bits(alive);
memo[key] = ret;
return ret;
}
int ans = count_bits(alive);
// 枚举所有合法的攻击者-目标对。
for (int i = 0; i < n; i++) {
if (!(alive & (1 << i)) || (used & (1 << i))) {
continue;
}
for (int j = 0; j < n; j++) {
if (i == j || !(alive & (1 << j))) {
continue;
}
int next_alive = alive;
int next_used = used | (1 << i);
if (r[i] > r[j]) {
next_alive &= ~(1 << j); // 击杀目标
}
ans = min(ans, dfs(next_alive, next_used));
}
}
memo[key] = ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (ll i = 0; i < n; i++) {
cin >> r[i];
}
memo.clear();
cout << dfs((1 << n) - 1, 0) << '\n';
return 0;
}暴力的状态数是指数级的，无法处理 n=10^5。
关键点是：一只怪兽可以先攻击别人，之后再被更强的怪兽击败。因此我们不需要纠结具体攻击顺序，可以把一次有效攻击看成一对匹配：
攻击者的 r > 被击败者的 r也就是说，我们有两份相同的怪兽集合：一份作为攻击者，一份作为被击败者。每张牌在攻击者侧最多用一次，在被击败者侧最多用一次。目标是最多配出多少对 r_attacker > r_victim。
排序后用双指针贪心即可：
- 把所有
r_i从小到大排序； victim指向当前最弱的待击败怪兽；attacker从小到大扫描攻击者；- 如果
r[attacker] > r[victim]，就用它击败victim，匹配数加一； - 否则这个攻击者连最弱目标都打不过，只能跳过。
为什么这样是对的？如果当前攻击者打不过最弱目标，它也打不过任何更强目标，跳过不会损失答案。如果当前攻击者能打过最弱目标，用这个“最弱可行攻击者”去击败当前最弱目标最省强牌，不会比用更强怪兽更差。
设最大可击败数为 killed，那么最少剩余怪兽数就是：
n - killed代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-01 22:49
* update_at: 2026-10-01 22:49
*/
// main.cpp：满分做法，排序后用双指针贪心：给每个最弱目标找最弱的能击杀它的攻击者。
// 核心思路：排序后，如果当前攻击者能杀当前目标就杀，否则攻击者后移。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll n;
int r[MAXN]; // 每只怪兽的攻击力/防御力（≤ 10^5，int 足够）
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> r[i];
}
// 按攻击力从小到大排序。
sort(r + 1, r + n + 1);
ll victim = 1; // 当前最弱的目标
ll attacker = 1; // 当前攻击者
ll killed = 0;
// 给每个当前最弱的目标，找一个尽量弱但严格更强的攻击者。
while (victim <= n && attacker <= n) {
if (r[attacker] > r[victim]) {
killed++;
victim++;
attacker++;
} else {
attacker++;
}
}
cout << n - killed << '\n';
return 0;
}复杂度
排序复杂度为
空间复杂度为
总结
这题容易被“攻击顺序”干扰。真正重要的是：怪兽可以先攻击再被击败，所以一次有效攻击只是在“攻击者拷贝”和“被击败者拷贝”之间建立一对严格大于关系。
把问题转成最大匹配后，排序加双指针就能得到最多能击败多少只怪兽。