题解 CF2164C Dungeon

JuRuoOIer · 2025-11-25 08:43:08 · 题解

题解 CF2164C Dungeon

其他题

题意

有 n 把剑，m 个怪，剑有攻击力 a_i，怪有防御力 b_j。剑 i 能杀死怪 j 当且仅当 a_i\ge b_j。

怪分两类：

一个怪只能打一次，求最多能打死多少怪。

数据范围：多测，\sum n,\sum m\le 2\times10^5，a_i,b_i,c_i\le 10^9。

做法

显然要先打能爆装备的怪。而为了尽量使剑增强，每个这种怪都应该用尽量烂的剑去打。为了防止有怪不强化就打不死的情况打的时候按 b_i 排个序。这可以用 multiset 维护，不会写也可以上树。

然后对于不爆装备的就枚举每个怪找最菜的剑打就行，顺序随意因为反正我每次用的是最菜的剑，打谁都一样。

:::success[代码] 关于 set 和 multiset 的基本操作：

set 里的元素是自动排序的（是的这个很多打了两三年的选手都不知道），所以使用迭代器遍历 set 即可得到从小到大的顺序。
set 底层是红黑树所以其迭代器是双向迭代器，不能进行加减（无论与其他迭代器还是与整数），只能借助 ++ 或 -- 操作一格一格移动；也不能比大小，所以使用迭代器遍历时需要写 for(set<ll>::iterator i=s.begin();i!=s.end();i++)，其中 ll 换成你所开 set 的类型，s 换成你所开 set 的名称。
set 里有一个成员叫做 lower_bound()，传入键类型值，返回迭代器，可以在 set 中进行二分查找。还有一个成员是 find()，传入和返回同上，也是二分查找。两者的区别是前者找的是第一个大于等于所传入值的值，而后者只找恰好等于所传入值的值，当找不到符合条件的值时两者都会返回 s.end()。
set 里有一个成员叫做 erase()，传入迭代器，可以在 set 中删除。
对于 priority_queue 能代替的需求，最好不要用 set，因为它常数巨大。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define lf double
#define ld long double
using namespace std;
struct node{
    ll b,c;
};
bool operator <(node x,node y){
    return x.b==y.b?x.c>y.c:x.b<y.b;
}
ll T,n,m,u,b[200010],p1,p0,ans;
multiset<ll> s;
node c[200010];
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        s.clear();p0=p1=ans=0;
        for(int i=0;i<n;i++){
            cin>>u;
            s.insert(u);
        }
        for(int i=0;i<m;i++){
            cin>>b[i];
        }
        for(int i=0;i<m;i++){
            cin>>u;
            if(u){
                c[p1].b=b[i];
                c[p1++].c=u;
            }
            else{
                b[p0++]=b[i];
            }
        }
        sort(b,b+p0);
        sort(c,c+p1);
        for(int i=0;i<p1;i++){
            set<ll>::iterator p=s.lower_bound(c[i].b);
            if(p==s.end()){
                break;
            }
            ans++;
            ll tmp=(*p);
            s.erase(p);
            s.insert(max(tmp,c[i].c));
        }
        for(int i=0;i<p0;i++){
            set<ll>::iterator p=s.lower_bound(b[i]);
            if(p==s.end()){
                break;
            }
            ans++;
            s.erase(p);
        }
        cout<<ans<<endl;
    }
    return 0;
}

:::