复赛一：决斗（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++，表示下一个弱怪兽成为新的目标。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**************************************************************** 
 * 代码作者: 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;  // 总数 - 被消灭的 = 剩余数量
}
Previous Topic
Back to Lesson
Next Topic