POJ 3061 Subsequence — 前綴和 + 二分查找 O(n log n) 解法

問題描述

給定長度 N (10 < N < 100,000) 的正整數序列（每個 ≤ 10000）與目標和 S (< 100,000,000)。求連續子序列和 ≥ S 的最小長度，不存在輸出 0。

前綴和 + 二分

計算前綴和 sum[i]（sum[0]=0）。對每個起點 s，需找最小 t 使 sum[t] - sum[s] ≥ S，即 sum[t] ≥ sum[s] + S。因 sum 遞增，可用 lower_bound 二分查找。

參考代碼 (C++)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[100000], n, S;
int sum[100001];

void solve() {
    for (int i = 0; i < n; ++i) sum[i+1] = sum[i] + a[i];
    if (sum[n] < S) { printf("0\n"); return; }

    int res = n;
    for (int s = 0; sum[s] + S <= sum[n]; ++s) {
        int t = lower_bound(sum + s, sum + n + 1, sum[s] + S) - sum;
        res = min(res, t - s);
    }
    printf("%d\n", res);
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> S;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        solve();
    }
    return 0;
}

關鍵點

• lower_bound 返回首個 ≥ 目標值的迭代器，恰好滿足條件。
• 外層循環 s 只需遍歷到 sum[s] + S ≤ sum[n]，剪枝明顯。
• 時間 O(n log n)，空間 O(n)，n=100,000 極快。

同類函數

• upper_bound：首個 > 目標值的迭代器。
• 均基於二分查找，要求序列有序。