复赛一：决斗（duel）

洛谷：P11231 OJ：P7056

有 n 只怪兽，第 i 只怪兽的攻击力和防御力都是 ri。
规则：
1. 每只怪兽最多只能主动攻击一次；
2. 攻击时，如果攻击力 ≤ 防御力，对方不死；
3. 如果攻击力 > 防御力，被攻击怪兽出局；
4. 游戏结束条件：所有仍在场的怪兽都已经攻击过一次。
目标：设计攻击顺序，使 剩下未退出的怪兽数量最小。

维护两个指针：
- i 表示当前作为攻击者的怪兽（从小到大走）。
- j 表示当前“最弱的还活着的怪兽”。
对于每个攻击者（注意到 i+1 位置），尝试消灭最弱的怪兽 a[j]。
如果 a[i+1] > a[j]（攻击者比防御者强），就能消灭 a[j]：
- 消灭数 cnt++
- 指针 j++，表示下一个弱怪兽成为新的目标。

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-04-21 18:50:00
 * 最后修改: 2025-10-02 16:09:11
 * 文件描述: [CSP-S 2024] 决斗
****************************************************************/

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        int b;
        cin>>b;
        a[i]=b;
    }
    sort(a.begin(),a.end());   // 排序：攻击力/防御力都按从小到大排列
    
    int cnt=0; // 记录能消灭的怪兽数
    int j=0;   // 指向当前“最弱的还没死的怪兽”
    for(int i=0;i<n-1;i++){   // 枚举攻击者
        if(a[i+1]>a[j]){  // 如果比最小的还强，就能杀掉它
            cnt++;        // 成功击杀一个
            j++;          // j前移，表示下一个“最弱怪兽”
        }      
    }
    cout<<n-cnt;  // 总数 - 被消灭的 = 剩余数量
}

信息学奥赛历年真题

复赛一：决斗（duel）

题目回顾