题解
1.最笨的想法,链表,每次在还没被杀死的怪物里遍历一遍,如果被杀死了就从链表中删除这个节点
但是TLE on #7
2.进阶想法,仍然是链表,我们想,如果有些怪物永远都不会被杀死,那我们就没必要遍历它。所以我们从可能被杀死的怪物中遍历
如果一个怪物这个回合被杀死,但是在上个回合中没有被杀死,说明它的两侧怪物发生了变动,说明了上个回合它的两侧怪物被杀死了
所以优化方法如下:一开始把所有的怪物都放进第一回合可能被杀死的集合中,然后遍历集合,如果有怪物被杀死,其两侧的怪物放入下一回合可能被杀的集合中
code
#include<bits/stdc++.h>
using namespace std;
int a[300005]={0},b[300005]={0};
struct
{
int l,r,a,b;
}gw[300005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
gw[0].a=0,gw[0].b=0;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>gw[i].a;
for(int i=1;i<=n;i++)cin>>gw[i].b;
set<int> maybe;//代表可能被删的怪物
for(int i=1;i<=n;i++)
{
gw[i].l=i-1;
gw[i].r=i+1;
maybe.insert(i);
}
gw[n].r=0;
int out[300005]={1};//初始化0已被删
for(int i=1;i<=n;i++)
{
vector<int> dellist;
for(int j : maybe)
{
int L=gw[j].l,R=gw[j].r;
if(gw[j].b<gw[L].a+gw[R].a&&!out[j]) dellist.push_back(j);//如果不判断out,被删掉的元素还有可能继续被删
//先放再删是因为攻击是同时进行的,还需要当前怪物的配合
}
maybe.clear();
cout<<dellist.size()<<" ";
for(int j=0;j<dellist.size();j++)
{
int now=dellist[j];
out[now]=1;//代表已被删
int L=gw[now].l,R=gw[now].r;
gw[L].r=R;
gw[R].l=L;
maybe.insert(L);
maybe.insert(R);
}
}
cout<<endl;
}
return 0;
}
标签:gw,遍历,int,Monsters,回合,怪物,杀死,Berserk
From: https://www.cnblogs.com/pure4knowledge/p/17981091