卡牌题解(CSP2024ST1改)

前言

1. 本题为训练题，应该是CSP2024ST1改
2. 思维性简单题目
3. 代码是我写的题解是AI写的

问题描述

在这道题中，我们需要优化卡牌怪兽的攻击顺序，以最小化游戏结束时剩余的怪兽数量。具体来说：

• 给定 n 张怪兽卡，每张卡有攻击力 a_i 和防御力 d_i，且保证 a_i \leq d_i。
• 游戏由若干回合组成，每回合可以选择一只怪兽 i 向另一只怪兽 j 发起攻击（i \neq j）。
• 如果 a_i > d_j，则怪兽 j 的防御被打破，退出游戏；否则，无任何变化。
• 每只怪兽在整个游戏中最多只能发起一次攻击。
• 游戏在所有未退出的怪兽都已发起过攻击后结束。

目标是通过合理的攻击顺序和攻击目标选择，使游戏结束时剩余的怪兽数量最少。

解题思路

为了最小化剩余怪兽数，我们希望通过攻击尽可能多的怪兽使其退出游戏。具体策略如下：

1. 排序：

   • 将所有怪兽的攻击力 a 和防御力 d 分别排序，方便后续匹配。
   • 升序排列攻击力 a，升序排列防御力 d。

2. 匹配攻击与防御：

   • 使用双指针方法，同时遍历攻击力数组和防御力数组。
   • 对于当前的攻击力 a[i]，尝试找到最小的防御力 d[j] 使得 a[i] > d[j]。
   • 如果找到这样的 d[j]，说明可以通过 a[i] 攻击 d[j]，使得怪兽 j 退出游戏。此时，增加成功攻击的计数 k，并将 j 指针右移，继续寻找下一个可以被攻击的防御力。
   • 如果当前 a[i] 无法攻击 d[j]（即 a[i] \leq d[j]），则跳过这个 d[j]，继续寻找更高的 a[i] 来攻击。

3. 计算结果：

   • 最终剩余的怪兽数量为总数 n 减去成功被攻击并退出的怪兽数量 k，即 n - k。

这种策略确保每次攻击都尽可能地利用较小的攻击力去击败较低的防御力，从而最大化被击败的怪兽数量。

代码思路

基于上述解题思路，代码的实现步骤如下：

1. 输入读取与排序：

   • 读取所有怪兽的攻击力和防御力。
   • 分别将攻击力和防御力数组进行升序排序。

2. 双指针匹配：

   • 初始化两个指针 i（遍历攻击力数组）和 j（遍历防御力数组），以及计数变量 k 来记录成功攻击的次数。
   • 遍历攻击力数组，对于每一个 a[i]，检查是否可以攻击当前的 d[j]。
   • 如果 a[i] > d[j]，则表示可以攻击，增加 k 并将 j 指针右移。
   • 重复此过程，直到遍历完所有攻击力或防御力。

3. 输出结果：

   • 输出 n - k，即剩余的怪兽数量。

代码注释

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

using ll =int64_t;

const ll maxn{ll(1e6+5)};
ll a[maxn],d[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n; // 读取怪兽数量
    for(int i=0;i<n;i++){
        cin >> a[i] >> d[i]; // 读取每个怪兽的攻击力和防御力
    }
    
    sort(a, a+n); // 将攻击力数组升序排序
    sort(d, d+n); // 将防御力数组升序排序
    
    int j = 0; // 指向防御力数组的指针
    int k = 0; // 记录成功攻击的次数
    for(int i=0;i<n;i++){
        if(a[i] > d[j]){
            k++;    // 成功攻击，计数增加
            j++;    // 指向下一个防御力
            if(j == n){
                break; // 如果所有防御力都已匹配，退出循环
            }
        }
    }
    cout << (n - k) <<'\n'; // 输出剩余的怪兽数量
}

总结

通过对怪兽的攻击力和防御力分别进行排序，并采用双指针的方法进行匹配，我们能够高效地计算出在最优攻击策略下，游戏结束时剩余的最少怪兽数量。该方法的时间复杂度为 O(n \log n)，适用于题目中 n 达到 10^6 的规模，满足题目的性能要求。此策略确保每次攻击都尽可能地将攻击力小的怪兽用于击败防御力低的怪兽，从而最大化被击败的怪兽数量，最终实现最小化剩余怪兽数的目标。