[CSP-S 2024] 决斗

GitHub跳转原题关系图返回列表

把有效攻击看成强牌匹配弱牌，排序后用双指针求最多能击败多少只怪兽。

OJ: luogu

题目 ID: P11231

难度:普及/提高-

标签:贪心排序

日期: 2026-06-22 18:23

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 n 只怪兽，第 i 只怪兽的攻击力和防御力都等于 r_i。

每回合可以选择一只还在场的怪兽 i，让它攻击另一只还在场的怪兽 j。如果 r_i > r_j，则 j 退出游戏；否则无事发生。每只怪兽整场游戏中至多发起一次攻击。

要求安排攻击顺序，使最后剩余怪兽数量最少。

思路

先看一个小数据暴力：用 alive 记录还活着的怪兽，用 used 记录已经攻击过的怪兽，递归枚举下一次攻击的攻击者和目标。

cpp
// brute.cpp：小数据搜索所有攻击顺序，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int n;
int r[MAXN];
map<long long, int> memo;

int count_bits(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

int dfs(int alive, int used) {
    long long key = ((long long)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 (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    memo.clear();
    cout << dfs((1 << n) - 1, 0) << '\n';

    return 0;
}

暴力的状态数是指数级的，无法处理 n=10^5。

关键点是：一只怪兽可以先攻击别人，之后再被更强的怪兽击败。因此我们不需要纠结具体攻击顺序，可以把一次有效攻击看成一对匹配：

text
攻击者的 r > 被击败者的 r

也就是说，我们有两份相同的怪兽集合：一份作为攻击者，一份作为被击败者。每张牌在攻击者侧最多用一次，在被击败者侧最多用一次。目标是最多配出多少对 r_attacker > r_victim。

排序后用双指针贪心即可：

  1. 把所有 r_i 从小到大排序；
  2. victim 指向当前最弱的待击败怪兽；
  3. attacker 从小到大扫描攻击者；
  4. 如果 r[attacker] > r[victim]，就用它击败 victim，匹配数加一；
  5. 否则这个攻击者连最弱目标都打不过，只能跳过。

为什么这样是对的？如果当前攻击者打不过最弱目标，它也打不过任何更强目标，跳过不会损失答案。如果当前攻击者能打过最弱目标，用这个“最弱可行攻击者”去击败当前最弱目标最省强牌，不会比用更强怪兽更差。

设最大可击败数为 killed，那么最少剩余怪兽数就是：

text
n - killed

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int r[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }

    sort(r + 1, r + n + 1);

    int victim = 1;
    int attacker = 1;
    int killed = 0;

    // 给每个当前最弱的目标，找一个尽量弱但严格更强的攻击者。
    while (victim <= n && attacker <= n) {
        if (r[attacker] > r[victim]) {
            killed++;
            victim++;
            attacker++;
        } else {
            attacker++;
        }
    }

    cout << n - killed << '\n';

    return 0;
}

复杂度

排序复杂度为 O(nlogn)O(n log n)，双指针扫描复杂度为 O(n)O(n)。

空间复杂度为 O(n)O(n)。

总结

这题容易被“攻击顺序”干扰。真正重要的是：怪兽可以先攻击再被击败，所以一次有效攻击只是在“攻击者拷贝”和“被击败者拷贝”之间建立一对严格大于关系。

把问题转成最大匹配后，排序加双指针就能得到最多能击败多少只怪兽。