本文主要是介绍D. Berserk Monsters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Monocarp（又一次）在玩电脑游戏。你猜他在做什么？没错，杀死怪物。
一排有 n 个怪物，编号从 1 到 n。第 i 个怪物有两个参数：攻击值等于 ai，防御值等于 di。为了杀死这些怪物，Monoccarp给它们施了一个狂暴咒语，所以它们相互攻击，而不是Monocarp的角色。
这场战斗由 n 轮组成。每一轮，都会发生以下情况：
首先，每一个活着的怪物i都会对左边最近的活着的怪物（如果存在的话）和右边最接近的活着的怪兽（如果存在）造成 ai 伤害；
然后，每一个在这一轮中受到超过 dj 伤害的活着的怪物 j 都会死亡。
第 j 个怪物死亡，当且仅当其防御值 dj 严格小于本轮受到的总伤害时。
对于每一轮，计算在该轮中死亡的怪物数量。
输入
第一行包含一个整数t（1 ≤ t ≤ 1e4）——测试用例的数量。
每个测试用例由三行组成：第一行包含一个整数 n（1 ≤ n ≤ 3e5）；第二行包含n个整数a1，a2，…，an（1 ≤ ai ≤ 1e9）；第三行包含 n 个整数 d1，d2，…，dn（1 ≤ di ≤ 1e9）。
对输入的附加约束：所有测试用例的 n 之和不超过 3e5。
输出
对于每个测试用例，打印 n 个整数。第 i 个整数应该等于第 i 轮中死亡的怪物数量。
Input
3
5
3 4 7 5 10
4 9 1 18 1
2
2 1
1 3
4
1 1 2 4
3 3 4 2
Output
3 1 0 0 0
0 0
1 1 1 0
注：
示例的第一个测试用例说明：
在第一轮中，会发生以下情况：
怪物1对怪物2造成3点伤害；
怪物2对怪物1和怪物3造成4点伤害；
怪物3对怪物2和怪物4造成7点伤害；
怪物4对怪物3和怪物5造成5点伤害；
怪物5对怪物4造成10点伤害；
怪物1不会死亡，因为它受到了4点伤害，防御为4点；
怪物2死亡，因为它受到10点伤害，防御为9点；
怪物3死亡，因为它受到9点伤害，防御为1；
怪物4没有死亡，因为它受到了17点伤害，防御是18点；
怪物5死亡，因为它受到5点伤害，防御为1。
第一轮过后，怪物1和4仍然活着。
在第二轮中，会发生以下情况：
怪物1对怪物4造成3点伤害；
怪物4对怪物1造成5点伤害；
怪物1死亡，因为它受到5点伤害，防御为4点；
怪物4不会死亡，因为它受到了3点伤害，防御是18点。
在接下来的三轮比赛中，只有第4个怪物还活着，所以什么也没发生。
解析：
容易想到记录每次活着的怪物的相邻项，再相加与d[i]比较，记录被杀死的个数，更新新的数列，不过这样做肯定超时！
第 i 轮被杀死的怪兽一定是上一轮被杀死的怪兽的相邻项，因为该项的上一轮相邻项的怪兽被杀，相邻项的数据产生了变动，否则上一轮杀不死它，这一轮还是杀不死它。
这样我们就只需要记录每次变动的且还没被杀死的相邻项怪兽，每次更新它们的相邻项即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,m;
int a[N],d[N],l[N],r[N];
bool vis[N];
set <int> s,p;
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>a[i];for (int i=1;i<=n;i++) cin>>d[i];for (int i=1;i<=n;i++){l[i]=i-1;r[i]=i+1;vis[i]=1;}r[n]=0; //强调一下，初始化！！！s.clear(),p.clear();for (int i=1;i<=n;i++) s.insert(i);int m=n;while (m--){for (auto x:s){if (a[l[x]]+a[r[x]]>d[x]) {vis[x]=0;p.insert(x);}}cout<<p.size()<<" ";s.clear();for (auto x:p){l[r[x]]=l[x]; //更新r[x]的左邻项r[l[x]]=r[x]; //更新l[x]的右邻项if (vis[l[x]]) s.insert(l[x]); //没被杀死的怪兽才可以进入下一轮if (vis[r[x]]) s.insert(r[x]);}p.clear();}cout<<endl;
}
signed main()
{ios;int T=1;cin>>T;while (T--) solve(); return 0;
}这篇关于D. Berserk Monsters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
