CF1922D Berserk Monsters 题解
zjinze
·
·
题解
前置知识： 双向链表。
思路：
我们可以先用结构体来建立一个双向链表，如：
struct node{
int pre;
int nxt;
}v[300010];
$v[i].nxt$ 表示第 $i$ 个怪物右侧的第一只存活的怪物的编号。
这时，我们定义 $2$ 个集合:$s$ 和 $ss$。
我们先令 $s$ 表示上这一轮攻击中牺牲的怪物，$ss$ 表示上一轮攻击中存活下来的怪物,$flag[i]$ 表示第 $i$ 个怪物是否退场。
初始化：
```cpp
for(int i=1;i<=n;i++){
ss.insert(i);
flag[i]=1;
}
```
这里解释一下，$flag[i]$ 的值为 $1$ 时，表示第 $i$ 个怪物还未退场；$ss$ 中应先放进所有元素，因为第一轮攻击时，所有怪物都必须参与。
紧接着，我们枚举每一轮攻击。
第一步：枚举 $ss$ 中的怪物，及上一轮攻击中存活下来的怪物，并判断该怪物会不会被左右两边的怪物攻击而死亡，如果会，我们将这个怪物进行永久标记，表示该怪物已经退场，并将该怪物放进 $s$ 中。
第二步：枚举完后，我们将 $ss$ 清空，并枚举 $s$ 中的怪物，及上一轮攻击中牺牲的怪物。这时，我们将双向链表进行修改：
```cpp
for(set<int>::iterator iter=s.begin();iter!=s.end();++iter){
v[v[*iter].pre].nxt=v[*iter].nxt;
v[v[*iter].nxt].pre=v[*iter].pre;
}
```
修改完双向链表后，我们再次跟新 $ss$ 的值。
但这时，我们不难发现如果在这一轮中，第 $x$ 个怪物还没有退场，说明第 $x+1$ 个怪物和第 $x-1$ 个怪物的攻击之和小于等于 $d[x]$。如果第 $x+1$ 个怪物和第 $x-1$ 个怪物在这一轮攻击中都没有退场的话，那么在下一轮攻击中，第 $x$ 个怪物也不会退场。
知道了这些，我们就只需把这一轮攻击中退场的怪物的左侧的怪物和这一轮攻击中退场的怪物的右侧的怪物丢到 $ss$ 里就行了。但是记得，如果这一轮攻击中退场的怪物的左侧的怪物和这一轮攻击中退场的怪物的右侧的怪物已经退场的话，就不要再丢到 $ss$ 里。这样就可以让原本的 $85$ 分蹦到 $100$ 分。
最后呢，我们要把 $s$ 给清空，并重复以上步骤直至枚举完每一轮攻击。
#### code:
```cpp
#include <bits/stdc++.h>
using namespace std;
void write(long long x){
if(x < 0) putchar('-'), x = -x;
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
long long read(){
long long x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch>'9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int t,n,tot,st,last;
bool flag[300010];
long long a[300010],d[300010];
struct node{
int pre;
int nxt;
}v[300010];
set<int>s;
set<int>ss;
set<int>::iterator iter;
signed main(){
t=read();
while(t--){
n=read();
tot=n;
last=n;
for(int i=1;i<=n;i++){
a[i]=read();
if(i==1)v[i].pre=-1;
else v[i].pre=i-1;
if(i==n)v[i].nxt=-1;
else v[i].nxt=i+1;
}
for(int i=1;i<=n;i++){
d[i]=read();
ss.insert(i);
flag[i]=1;
}
for(int k=1;k<=n;k++){
if(tot!=0 && tot!=1){
s.clear();
int temp=st;
for(iter=ss.begin();iter!=ss.end();++iter){
if(d[*iter]-a[v[*iter].pre]-a[v[*iter].nxt]<0){
s.insert(*iter);
flag[*iter]=0;
}
}
ss.clear();
for(iter=s.begin();iter!=s.end();++iter){
v[v[*iter].pre].nxt=v[*iter].nxt;
v[v[*iter].nxt].pre=v[*iter].pre;
if(flag[v[*iter].pre])ss.insert(v[*iter].pre);
if(flag[v[*iter].nxt])ss.insert(v[*iter].nxt);
tot--;
}
}
write(last-tot);
putchar(' ');
last=tot;
}
putchar('\n');
}
return 0;
}
```