题目分析

这是一个贪心匹配问题。关键点：

1. 如果怪兽 (i) 攻击怪兽 (j) 且 (r_i > r_j)，则 (j) 被消灭
2. 每只怪兽只能攻击一次
3. 游戏结束条件：所有存活怪兽都攻击过

目标：最大化被消灭的怪兽数量。

核心思路

将怪兽按攻击力（防御力）排序。
贪心策略：让攻击力大的怪兽去消灭攻击力小的怪兽，这样可以最大化消灭数量。

但要注意：

• 被消灭的怪兽不能攻击
• 存活怪兽必须都攻击过

设最终存活怪兽数为 (k)，则被消灭的怪兽数为 (n - k)。
因为每只存活怪兽需要攻击一次，且攻击必须针对其他怪兽，所以存活怪兽数不能超过能提供攻击目标的怪兽数。

算法步骤

1. 对 (r) 排序
2. 使用双指针贪心匹配：
   • 指针 i 指向可能被消灭的小怪
   • 指针 j 指向可能发起攻击的大怪
   • 如果 (r[j] > r[i])，则可以消灭，两个指针移动
   • 否则无法消灭，只移动 i
3. 最终存活数 = (n - \text{匹配数})

正确性解释

排序后，让大攻击力怪兽消灭小攻击力怪兽是最优的，因为：

• 大怪消灭小怪不会浪费大怪的攻击机会
• 小怪无法消灭大怪，所以让小怪存活到最后更优
• 匹配数最大时，存活数最小

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    freopen("duel.in", "r", stdin);
    freopen("duel.out", "w", stdout);
    
    int n;
    cin >> n;
    vector<int> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    
    sort(r.begin(), r.end());
    
    int i = 0, j = 0;
    int eliminated = 0;
    
    // 双指针贪心匹配
    while (i < n && j < n) {
        if (r[j] > r[i]) {
            // 怪兽j可以消灭怪兽i
            eliminated++;
            i++; // 被消灭的怪兽
            j++; // 发起攻击的怪兽
        } else {
            j++; // 当前怪兽攻击力不够，看下一个
        }
    }
    
    // 存活数 = 总数 - 被消灭数
    cout << n - eliminated << endl;
    
    return 0;
}

复杂度分析

• 排序：(O(n \log n))
• 双指针匹配：(O(n))
• 总复杂度：(O(n \log n))，可过 (n \leq 10^5)

算法标签

• 贪心算法
• 排序
• 双指针
• 匹配问题

这个解法可以正确求出最小存活怪兽数量。