本文主要是介绍Educational Codeforces Round 161 (Rated for Div. 2)----＞D. Berserk Monsters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，思路：
1.这是一个模拟链表题，考察对链表的掌握和熟悉程度。在这这题当中有个坑点就是，当一个怪在这回合死了，他任然可以旁边的怪照成伤害（不能着急的给他删掉，不然会出问题）。
2.还有这题很容易就想到，暴力模拟但是时间复杂度：n^2级别是过不了的。所以要优化，找到循环当中那些步骤是冗余的。显然我们可以发现，当一只怪的在这回合没有死掉，且他左右两边的怪也没有死掉，那么下回合他肯定不会死掉。利用这个特点，我们可以用set记录每回合后，那些怪物可能会死掉。
二，代码：
#include <iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;const int N=3e5+10;int ne[N],pre[N];
int arr[N],brr[N];//记录标记那些怪已近死掉
bool st[N];void Solved() {int n;cin>>n;for(int i=1;i<=n;i++) cin>>arr[i];for(int i=1;i<=n;i++) cin>>brr[i];set<int> s;//当有多组输入时，预处理处理边界情况，会让后面代码很好写，可以不用特判了arr[n+1]=0;st[n+1]=false;for(int i=1;i<=n;i++){//数组模拟链表pre[i]=i-1;ne[i]=i+1;//刚开始所有怪物都可能死掉s.insert(i);//刚开始所有怪物都存活st[i]=true;}for(int i=1;i<=n;i++){//将这回合已近死了的怪物，存起来不要马上删掉set<int> temp;int cnt=0;//判断那些怪物已经死掉了，并标记for(auto t: s){if(arr[pre[t]]+arr[ne[t]]>brr[t]){temp.insert(t);st[t]=false;}}s.clear();//处理删除操作，把下回合可能死掉的怪物存起来for(auto t:temp){cnt++;//假如怪物在这回合已经死了的话，就不要等到下一回合了if(st[pre[t]]) s.insert(pre[t]);if(st[ne[t]]) s.insert(ne[t]);//链表删除操作pre[ne[t]]=pre[t];ne[pre[t]]=ne[t];}cout<<cnt<<" ";}cout<<endl;
}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}这篇关于Educational Codeforces Round 161 (Rated for Div. 2)----＞D. Berserk Monsters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
