您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU Non 循環移位前綴和非負：單調隊列優化 O(n) 解法

編輯：關於C++

問題描述

長度 n（≤10⁶）序列，循環左移 k 位（0≤k

核心轉化

序列複製一遍拼接成長度 2n。原問題等價於：在長度 2n 的前綴和數組 sum[i] 中，找長度為 n 的滑動窗口，使得窗口內最小值 ≥ 窗口起始位置前的值（即 min_{i∈[k+1,k+n]} sum[i] ≥ sum[k]）。

單調隊列維護滑動窗口最小值

隊列存下標，單調遞增（隊首最小）
入隊：彈出隊尾所有 ≥ 當前值的下標
出隊：隊首下標 < 窗口左邊界則彈出

完整代碼

#include 
using namespace std;
const int MAXN = 2000005;

int n, a[MAXN];
long long sum[MAXN];
int q[MAXN], head, tail;

void push(int i) {
    while (head < tail && sum[i] <= sum[q[tail-1]]) --tail;
    q[tail++] = i;
}

void pop(int i, int window_len) {
    if (q[head] <= i - window_len) ++head;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n, n) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            sum[i] = sum[i-1] + a[i];
        }
        for (int i = n+1; i <= 2*n; ++i)
            sum[i] = sum[i-1] + a[i-n];
        
        head = tail = 0;
        int ans = 0;
        // 初始化前 n-1 個元素進隊
        for (int i = 1; i < n; ++i) push(i);
        
        // 滑動窗口 [i-n+1, i] 對應移位 k = i-n
        for (int i = n; i <= 2*n; ++i) {
            push(i);
            pop(i, n);
            if (sum[q[head]] >= sum[i-n]) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵點解析

步驟	說明
拼接數組	a[n+1..2n] = a[1..n]，前綴和同理延伸
窗口對應	窗口 [k+1, k+n] 對應移位 k，條件 min(sum) ≥ sum[k]
隊列初始化	先放入前 n-1 個，第 n 個開始完整窗口
出隊條件	下標 ≤ i-n 視為超出窗口左邊界