Napoleon Cake

簡易題敘

題目給你 tt 組測資,每組測資有 nn 個數字(nn 是蛋糕大小),一開始蛋糕是乾的,aia_i 代表從 ii 開始往下數 aia_i 個(包含 ii 自己)的蛋糕都有被淋濕,超過底部沒關係,求最後蛋糕各層有沒有濕,是濕的就輸出 11,乾的輸出 00

範例測資:

  • 輸入
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
  • 輸出
1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 0 

概念講解

首先,因為一開始蛋糕是乾的,我們將差分陣列 difdif 初始化為 00

memset(dif, 0, sizeof(dif));

輸入 aia_i 時,如果是 00 直接不理它,不是的話就在頭尾加 1111(注意,超過第一層的要算到第一層,也就是三元運算子那塊)

for (int i = 1, x; i <= n; i++) {
    cin >> x;
    if (!x) continue;
    dif[(i - x + 1 > 0 ? i - x + 1 : 1)]++;
    dif[i + 1]--;
}

跑一遍每個位置的前綴和,大於 00 代表有淋濕,輸出 11,否則是 00

int now = 0;
for (int i = 1; i <= n; i++) {
    now += dif[i];
    cout << (now > 0 ? 1 : 0) << ' ';
}

範例程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int t, n, dif[N];
signed main() {
    cin >> t;
    while (t--) {
        cin >> n;
        memset(dif, 0, sizeof(dif));
        for (int i = 1, x; i <= n; i++) {
            cin >> x;
            if (!x) continue;
            dif[(i - x + 1 > 0 ? i - x + 1 : 1)]++;
            dif[i + 1]--;
        }
        int now = 0;
        for (int i = 1; i <= n; i++) {
            now += dif[i];
            cout << (now > 0 ? 1 : 0) << ' ';
        }
        cout << '\n';
    }
}