HDU 4193 單調隊列解環形數組前綴和非負問題

問題描述

給定長度為 n 的環形數組，求以多少個位置為起點，使得從該位置開始的前綴和均非負（即沿環走一圈，任意前綴和 ≥ 0）。

核心思路：前綴和 + 單調隊列滑動窗口最小值

1. 將環形數組展開為長度 2n 的線性數組 a[1..2n]，a[i+n] = a[i]。
2. 計算前綴和 sum[0]=0; sum[i]=sum[i-1]+a[i]。
3. 對於以位置 i (n ≤ i < 2n) 為終點的長度 n 子數組，其起點為 i-n+1。該子數組所有前綴和非負 ⇔ 窗口 [i-n+1, i] 內的 sum[j] - sum[i-n] ≥ 0 ⇔ 窗口內 sum 最小值 ≥ sum[i-n]。
4. 維護一個單調遞增隊列存儲 sum 的索引，隊首始終為當前窗口最小值。滑動窗口大小固定為 n。

算法流程

int front = 0, rear = 0, ans = 0;
for (int i = 1; i <= 2*n; ++i) {
    // 維護單調性：從隊尾刪除 >= sum[i] 的元素
    while (front < rear && sum[i] < sum[id[rear-1]]) --rear;
    id[rear++] = i;
    // 窗口形成（i >= n）時檢查條件
    if (i >= n) {
        if (sum[id[front]] >= sum[i-n]) ++ans;
        // 移除滑出窗口的元素
        if (id[front] == i-n+1) ++front;
    }
}

關鍵點

• 前綴和數組長度 2n，sum[0] 參與比較。
• 單調隊列存索引而非值，方便判斷是否滑出窗口。
• 隊列遞增保證隊首為窗口最小值。

複雜度

• 時間：O(n) — 每個元素進隊出隊各一次。
• 空間：O(n) — 隊列與前綴和數組。

總結

HDU 4193 是單調隊列求滑動窗口最小值的經典應用。將環形問題展開為線性、轉化為前綴和差值條件、再用單調隊列維護窗口最小值，是解決此類問題的標準套路。