CF1923B Monsters Attack! 题解

题目简述

数轴上有 $n$ 个怪兽。最初第 $i$ 个怪兽在 $x_i$ 位置上，且血量为 $a_i$。你在位置 $0$ 上。

在每秒钟会发生：

• 你给任意怪兽发射总共 $k$ 颗子弹，受到攻击的怪兽血量减一。
• 血量小于等于 $0$ 的怪兽死亡。
• 没有死亡的怪兽向你移动一个单位。
• 当一个怪兽来到你的位置，你就输了。

问你能不能赢。

$1 \le k \le 2 \times 10^9$，$1 \le a_i \le 10^9$，$-n \le x_1 < x_2 < x_3 < \cdots < x_n \le n$。

题目分析

首先我们发现位于 $x$ 的怪兽会在 $\lvert x \rvert$ 秒到达 $0$ 点，这启发我们可以用一个桶统计第 $i$ 秒到达的怪兽的总血量。

接下来，我们考虑贪心，策略是先打先到的怪兽。有了思路，我们直接模拟即可。具体来说，就是维护剩余的子弹数量，每过一秒加上 $k$，如果剩余的子弹数量大于等于这一秒到来的怪兽的总血量，那么减去它即可，否则就是输了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
long long t,n,k,pos[N],sum;
struct foreigner
{
	long long a,x;
}b[N];
void solve()
{
	sum=0;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].a;
		pos[i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].x;
		pos[abs(b[i].x)]+=b[i].a;
	}
	for(int i=1;i<=n;i++)
	{
		sum+=k;
		if(sum<pos[i])
		{
			printf("No\n");
			return;
		}
		else sum-=pos[i];
	}
	printf("Yes\n");
	return;
}
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cin>>t;
   while(t--)
   {
    	solve();
   }
   return 0;
}