题解 CF2164C Dungeon

题意

有

n

把剑，

m

个怪，剑有攻击力

a_i

，怪有防御力

b_j

。剑

i

能杀死怪

j

当且仅当

a_i\ge b_j

。

怪分两类：

$c_i=0$ 的怪打完后剑会爆掉。
$c_i>0$ 的怪打完后剑的攻击力会变为原攻击力与 $c_i$ 中的较大值。

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

数据范围：多测，

\sum n,\sum m\le 2\times10^5

，

a_i,b_i,c_i\le 10^9

。

做法

显然要先打能爆装备的怪。而为了尽量使剑增强，每个这种怪都应该用尽量烂的剑去打。为了防止有怪不强化就打不死的情况打的时候按

b_i

排个序。这可以用 multiset 维护，不会写也可以上树。

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

代码

关于 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，因为它常数巨大。

CPP

#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;
}

题解 CF2164C Dungeon

文章操作

题解 CF2164C Dungeon

题意

做法

相关推荐

评论

题解 CF2164C Dungeon