CF1763B Incinerate

题意

为了消灭人类，怪物协会向地球表面派出了 \(n\) 只怪兽。第 \(i\) 只怪物有一个生命值 \(h_i\) 和一个攻击力 \(p_i\) .

凭借他最后的一击，真螺旋焚烧炮，Genos 可以对所有活着的怪物造成 \(k\) 点伤害。换句话说，Genos 可以通过一次攻击降低所有怪物 \(k\) 点生命值（如果 \(k>0\)）。

然而，在 Genos 发动的每一次攻击之后，怪物们都会反击。在他们的共同努力下，它们通过活着的最弱的怪物的力量降低 Genos 的攻击伤害。换句话说，在每次攻击后，将\(k\)的值减去当前所有活着的怪物中的最小\(p_i\)。

最弱的怪物是力量最小的怪物。

如果怪物的生命值严格大于0，则它是活着的。

Genos 会成功杀死所有怪物吗？

思路

既然题目中已经提到了，每次都取最小的 \(p_i\) ，那很容易想到可以用优先队列进行模拟

同时，还需要将其与对应的 \(h_i\) 进行配对，可以在再其中套一层 pair

接着就直接模拟题目中的操作就好，每次都从队头依次查找没有死的最小的 \(p_i\) ，然后更新 \(k\) 为 \(k-p_i\) 即可

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
int n,k,now,ans,maxn;
int h[Maxn],p[Maxn];
void run()
{
	priority_queue<pair<int,int> >q; //first存p，second存h，默认按-p从大到小排序 
	cin>>n>>k;
    now=k;ans=1;maxn=-1e9;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		maxn=max(maxn,h[i]);
	}
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=n;i++) q.push(make_pair(-p[i],h[i]));
	while(now<maxn && k>0 && !q.empty())
    //now只要大于maxn，就一定可以杀死所有怪物
    //k小于0时，就无法对怪物造成实质性的伤害
	{
		while(!q.empty() && q.top().second<=now) q.pop(); //找到还活着的怪物的p[i]的最小值
		pair<int,int>t=q.top();
        q.pop();
		k+=t.first;
		now+=k;
		q.push(t);
	}
	while(!q.empty() && ans)//最后判断，是否全部的怪物都能被杀死
	{
		if(q.top().second>now) ans=0;
		q.pop();
	}
	cout<<(ans?"Yes":"No")<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
}