题解归档 - cf321B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf321B
• 本地来源：problems/cf321B/idea.md
• 题目链接：https://codeforces.com/contest/321/problem/B
• 原始标题：CF321B — Ciel and Duel

思路

CF321B — Ciel and Duel

题意

Jiro 有 n 张卡（ATK / DEF + 强度），Ciel 有 m 张全是 ATK 的卡。Ciel 每张卡最多用一次，可任意时刻结束。

• 打 ATK：己方强度 ≥ 对方，伤害 = 差值，对方死亡
• 打 DEF：己方强度 > 对方，对方死亡，无伤害
• Jiro 无存活卡时，下一张 Ciel 卡造成 全额 伤害

求 Jiro 受到的最大总伤害。

思路

排序后两种策略取 max：

策略 A — 只打 ATK，不要求清场

Ciel 升序、Jiro 的 ATK 升序。从 Ciel 最大 的卡往小扫，依次匹配当前最小的未匹配 ATK（双指针 k 从 0 增）。大 Ciel 配小 ATK 才能避开「1001 打 1000 只赚 1」的浪费。

策略 B — 清场（DEF + 全部 ATK + 直伤）

1. DEF 升序：用当前最小的、严格大于 DEF 的 Ciel 卡（浪费最少）
2. 剩余 Ciel 升序、ATK 升序：从小到大为每个 ATK 找最小可用 Ciel（≥ ATK）
3. 若全部匹配成功，剩余 Ciel 强度全部加进答案

复杂度

O(n log n + m log m)，排序主导。

样例

• 样例 2：策略 A 得 992（1001−100 + 101−10），不必击杀 ATK 1000
• 样例 3：ATK 0 可被 0 击杀；DEF 0 需 >0 的卡

结论

经典贪心，两种路径取 max。对拍 500 组通过（WSL，Kali 离线）。

代码

来源：problems/cf321B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:58:59
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=105;
ll a[maxn],atk[maxn],defv[maxn],usd[maxn];
int main(){
    ll n,m,i,j,k,na,nd,idx,ans,res,ok;
    string s;
    cin>>n>>m;
    na=0;
    nd=0;
    for(i=0;i<n;i++){
        cin>>s>>k;
        if(s=="ATK"){
            atk[na++]=k;
        }else{
            defv[nd++]=k;
        }
    }
    for(i=0;i<m;i++){
        cin>>a[i];
    }
    sort(a,a+m);
    sort(atk,atk+na);
    sort(defv,defv+nd);
    ans=0;
    res=0;
    k=0;
    for(j=m-1;j>=0;j--){
        if(k<na and a[j]>=atk[k]){
            res+=a[j]-atk[k];
            k++;
        }
    }
    ans=max(ans,res);
    for(i=0;i<m;i++){
        usd[i]=0;
    }
    idx=0;
    ok=1;
    for(i=0;i<nd;i++){
        while(idx<m and (usd[idx] or a[idx]<=defv[i])){
            idx++;
        }
        if(idx>=m){
            ok=0;
            break;
        }
        usd[idx]=1;
        idx++;
    }
    if(ok){
        res=0;
        idx=0;
        for(i=0;i<na;i++){
            while(idx<m and (usd[idx] or a[idx]<atk[i])){
                idx++;
            }
            if(idx>=m){
                ok=0;
                break;
            }
            res+=a[idx]-atk[i];
            usd[idx]=1;
            idx++;
        }
        if(ok){
            for(i=0;i<m;i++){
                if(!usd[i]){
                    res+=a[i];
                }
            }
            ans=max(ans,res);
        }
    }
    cout<<ans<<"\n";
    return 0;
}