题解：CF2164C Dungeon

BennyT · 2025-11-25 15:26:10 · 题解

题解：CF2164C Dungeon

思路

首先可以把怪物分为两类：c_i>0 和 c_i=0。

对于第一类，我们尽量用攻击力较弱的剑攻击，因为最终剑的攻击力是取 \max(x_i,c_i)，所以要让尽量攻击力小的剑的攻击力较大。

证明一下，我们设有两把剑攻击分别为 x,y 其中 x<y，有一个怪兽的 w<x,y。则当 c<x 时，最终两把剑的攻击不变；当 x\le c\le y 时，用 x 攻击最终两把剑的攻击分别为 c,y，用 y 攻击最终两把剑的攻击分别为 x,y，显然前者更优；当 x<y<c 时，用 x 攻击最终两把剑的攻击分别为 c,y，用 y 攻击最终两把剑的攻击分别为 x,c，显然前者更优。

由此可得，我们每次选择攻击力大于 w_i 并且攻击力最小的剑一定是不劣的。

接下来就好办了，使用平衡树维护即可。

对于第二类，我们参考ABC431C的思路，将最终剑的攻击与第二类怪兽按 a_i,w_i 从小到大排序，每次尝试用剑攻击此时 w_i 最小的怪物即可。

代码

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        for(int i=1;i<=id;i++){
            tr[i]={0,0,0,0,0};
        }
        id=rt=0;
        ins(2e9);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            ins(a[i]);
        }
        for(int i=1;i<=m;i++){
            cin>>b[i].w;
        }
        for(int i=1;i<=m;i++){
            cin>>b[i].c;
        }
        vector<N> x,y,z;
        for(int i=1;i<=m;i++){
            if(b[i].c>b[i].w){
                x.push_back(b[i]);
            }
            else if(b[i].c){
                y.push_back(b[i]);
            }
            else{
                z.push_back(b[i]);
            }
        }
        int ans=0;
        sort(x.begin(),x.end());
        for(N i:x){
            int p=getsuf(i.w);
            if(p==2e9)continue;
            del(p);
            ins(max(i.c,p));
            ans++;
        }
        for(int i=1;i<=n;i++){
            a[i]=getval(rt,i);
        }
        for(N i:y){
            if(i.w<=a[n])ans++;
        }
        int p=1;
        sort(z.begin(),z.end());
        for(N i:z){
            while(p<=n&&a[p]<i.w)p++;
            if(p<=n&&i.w<=a[p]){
                p++;
                ans++;
                if(p>n)break; 
            }
            else break;
        }
        cout<<ans<<'\n';
    }
    return 0;
}