SDUT 2778：小明的花費預算 - 二分答案法詳解

問題描述

小明 n 個月的花費已知，需將這 n 個月劃分為恰好 m 組，每組至少一個月、月份連續。目標是使各組總花費的最大值最小化。輸出這個最小的最大總花費。

範例

輸入：
5 3
3 2 9 4 1

輸出：9
解析：分組 [3,2] [9] [4,1] → 組和為 5, 9, 5 → 最大值 9，為最優。

核心思路：二分答案 + 貪心驗證

答案具有單調性：若某最大組和 mid 可行，則更大的值也可行；不可行則更小的值也不可行。故可二分答案。

驗證函數 check(mid)

• 遍歷月份，累加花費至當前組。
• 若加入下個月會超過 mid，則開新組。
• 統計所需組數 cnt，若 cnt ≤ m 則可行（可通過拆分組進一步減少最大值）。

參考代碼 (C++)

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

const int MAXN = 100010;
int n, m, a[MAXN];
int low, high;

bool check(int mid) {
    int cnt = 1, sum = 0;
    for (int i = 0; i < n; ++i) {
        if (sum + a[i] <= mid) sum += a[i];
        else { ++cnt; sum = a[i]; }
    }
    return cnt <= m;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        low = 0; high = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            low = max(low, a[i]); // 下界：最大單月花費
            high += a[i];         // 上界：所有月份總和
        }
        int ans = high;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (check(mid)) { ans = mid; high = mid - 1; }
            else low = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

• 二分範圍：[max(a_i), sum(a_i)]。
• 驗證貪心：盡量填滿當前組，超過即開新組，保證組數最少。
• 單調性證明：若 mid 可行，放寬限制（增大 mid）必可行；若不可行，收緊限制必不可行。
• 時間複雜度：O(n log(sum))，n ≤ 1e5，sum ≤ 1e10，極快。