開啟章節選單
Napoleon Cake
簡易題敘
題目給你 組測資,每組測資有 個數字( 是蛋糕大小),一開始蛋糕是乾的, 代表從 開始往下數 個(包含 自己)的蛋糕都有被淋濕,超過底部沒關係,求最後蛋糕各層有沒有濕,是濕的就輸出 ,乾的輸出 。
範例測資:
- 輸入
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
概念講解
首先,因為一開始蛋糕是乾的,我們將差分陣列 初始化為 。
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) << ' '; }
範例程式碼
#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'; } }