https://codeforces.com/contest/1922/problem/D
题目大意
给出 $n \ (1 \le n \le 3 \times 10^5)$ 长的两个数组 $a, d$，$1 \le a_i, d_i \le 10^9$，代表 $i$ 个怪物的血量和生命值。之后模拟 $n$ 轮，每轮：
- 活着的每个怪物 $i$ 同时向自己左右还活着的相邻的怪物造成 $a_i$ 点伤害。
- 本轮 $i$ 如果受到的伤害 $sum_i > b_i$ 则再本轮结束时死去。输出本轮死去的怪物数。
简要题解
直接模拟显然是 $O(n^2)$ 的。这无法通过。
注意到，如果一个怪物在上一轮的攻击中没有死去，且左右的怪物上一轮也没有死去，因此除了第一轮我们需要检查所有怪物状态以外，在之后的轮次只需要检查上轮死了的怪物旁边活着的怪物的状态即可。可以用双向链表或者 set 维护活着的怪物，用队列维护下一轮需要检查的怪物。(这也很像分层 BFS)
也就是说一共最多会有不到 $3n$ 次激活，$n$ 次第一轮，之后每删掉一个点，最多 $2$ 个激活。因此最多有 $O(n)$ 个元素进出队列。
注意，可能会连着删掉一串，或者一个元素左右都删掉了元素，注意不要重复处理。
这题也可以出成要多少轮达到稳定状态，因为最多只会有 $n - 1$ 个元素被删掉，且如果某轮没有删掉元素，就会达到稳态。
（可能我比较擅长这种题目，感觉这个题不够 1900）
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
struct DoubleLinkedList {
int n;
vector<int> l, r;
DoubleLinkedList(int n) : n(n), l(n + 2), r(n + 2) {
for (int i = 1; i <= n + 1; i++) {
l[i] = i - 1;
}
for (int i = 0; i <= n; i++) {
r[i] = i + 1;
}
}
PII erase(int id) { // check if id is valid
r[l[id]] = r[id];
l[r[id]] = l[id];
return {l[id], r[id]};
}
void show() {
int i = r[0];
while (i != n + 1) {
cout << i << ", ";
i = r[i];
}
cout << endl;
}
};
void solve() {
int n; cin >> n;
vector<int> a(n + 2), d(n + 2);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
DoubleLinkedList ls(n);
vector<int> valid(n + 2, 1);
valid[0] = valid[n + 1] = 0;
vector<int> inq(n + 1, 1);
vector<int> qu(n), tmp;
iota(qu.begin(), qu.end(), 1);
for (int ii = 0; ii < n; ii++) {
// cerr << ii << endl;
int m = qu.size();
tmp.clear();
for (int i = 0; i < m; i++) {
int u = qu[i];
inq[u] = 0;
int sum = 0;
sum += a[ls.l[u]];
sum += a[ls.r[u]];
// cerr << u << ' ' << sum << ' ' << d[u] << endl;
if (sum > d[u]) {
valid[u] = 0;
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
int u = qu[i];
if (valid[u]) continue;
auto [l, r] = ls.erase(u);
ans++;
if (valid[l] && !inq[l]) {
tmp.push_back(l);
inq[l] = 1;
}
if (valid[r] && !inq[r]) {
tmp.push_back(r);
inq[r] = 1;
}
}
swap(qu, tmp);
// ls.show();
cout << ans << (" \n"[ii == n - 1]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Increasing Subsequences - Educational Codeforces Round 161 (Rated for Div. 2)