题解：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

最小的怪物即可。

代码

CPP

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

题解：CF2164C Dungeon

文章操作

题解：CF2164C Dungeon

思路

代码

相关推荐

评论

题解：CF2164C Dungeon