按以下 \(n\) 次操作制作蛋糕。
- 叠上第 \(i\) 块面包，然后浇上 \(a_i\) 单位的奶油。可以使当前往下 \(a_i\) 块面包沾上奶油。
输出空格隔开的 \(n\) 个数，第 \(i\) 个的 \(0/1\) 代表第 \(i\) 块面包是否沾有奶油。
比较显然的思路可以进行差分修改。
view1
#include <bits/stdc++.h>
void solve(){
int n; std::cin >> n;
std::vector<int> a(n+2);
for (int i = 1; i <= n; i++) {
int d; std::cin >> d;
int l = std::max(1, i - d + 1), r = i;
a[l] += 1;
a[r + 1] -= 1;
}
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
for (int i = 1; i <= n; i++) std::cout << (a[i] == 0 ? 0 : 1) << " \n"[i==n];
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}
观察到每次修改只会往左一段修改，于是可以从右往左逆序统计。维护 \(cur\) 即当前位置往左需要浸透多少面包。
view2
#include <bits/stdc++.h>
void solve(){
int n; std::cin >> n;
std::vector<int> a(n+1), ans(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
int cur = 0;
for (int i = n; i; --i) {
cur = std::max(cur, a[i];)
if (cur > 0) cur -= 1, ans[i] = 1;
}
for (int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i==n];
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}