PAT 1044 Shopping in Mars：前綴和 + 二分查找優化區間和查詢

題目大意

火星購物：給定 N 個商品價格，目標金額 M。找出所有連續區間和 ≥ M 且最接近 M 的區間 [i, j]（輸出所有最優解）。N ≤ 10^5，暴力 O(N^2) 超時。

優化關鍵：前綴和 + 二分查找

定義前綴和 sum[i] = a[1] + ... + a[i]（sum[0]=0）。區間 [i, j] 和 = sum[j] - sum[i-1]。
對於固定 i，需找最小 j 使 sum[j] ≥ M + sum[i-1]。sum[] 遞增 → 二分查找 O(log N)。總體 O(N log N)。

完整邏輯

vector> ans;
int minDiff = INF;

for (int i = 1; i <= N; ++i) {
    int target = M + sum[i-1];
    int j = lower_bound(sum+i, sum+N+1, target) - sum; // 在 [i, N] 中查找
    if (j <= N) {
        int diff = sum[j] - sum[i-1] - M;
        if (diff < minDiff) {
            minDiff = diff;
            ans.clear();
            ans.emplace_back(i, j);
        } else if (diff == minDiff) {
            ans.emplace_back(i, j);
        }
    }
}

關鍵點

1. 前綴和轉化：區間和 → 兩前綴和之差。
2. 二分查找目標：target = M + sum[i-1]。
3. lower_bound：C++ STL 直接支援，返回首個 ≥ target 的位置。
4. 收集所有最優解：記錄 minDiff，等於時加入答案列表。

複雜度

• 前綴和構建：O(N)
• 主循環：N 次二分，O(N log N)
• 空間：O(N)

對比：雙指針法

因全正數，sum[] 嚴格遞增，亦可用雙指針 O(N) 滑動窗口。但二分寫法簡單、不易出錯，O(N log N) 完全通過。