POJ 3273 月度預算：二分答案求解最小最大月花費

題目大意

給定 N 天的花費記錄，需要將這 N 天分成 M 個連續的組（每組代表一個月），每組的花費為該組內天數花費之和。目標是找到一種分組方式，使得所有組中「最大花費」最小化。

解題思路：二分答案

這是一個典型的「二分答案」問題：

• 單調性：分組數越少，每組包含天數越多，最大花費越高；分組數越多，最大花費越低。具有單調性。
• 二分上下界：
  • 下界：max(每日花費) —— 至少要能容納單日最大花費
  • 上界：sum(所有花費) —— 全部天數合為一組
• 判定函數：給定一個最大花費限制 mid，檢查是否能在 M 個組內完成分組

判定邏輯詳解

bool judge(int N, int M, int mid, vector<int> a) {
    int sum = 0;      // 當前組累計花費
    int group = 1;    // 已使用組數
    
    for (int i = 0; i < N; i++) {
        if (sum + a[i] <= mid) {
            sum += a[i];           // 加入當前組
        } else {
            sum = a[i];            // 開啟新組
            group++;
        }
    }
    return group <= M;  // 組數不超過 M 則可行
}

完整代碼實現

#include <iostream>
#include <vector>
using namespace std;

bool judge(int N, int M, int mid, const vector<int>& a) {
    int sum = 0, group = 1;
    for (int i = 0; i < N; i++) {
        if (sum + a[i] <= mid) {
            sum += a[i];
        } else {
            sum = a[i];
            group++;
        }
    }
    return group <= M;
}

int main() {
    int N, M;
    while (cin >> N >> M) {
        vector<int> a(N);
        int maxVal = 0, sum = 0;
        
        for (int i = 0; i < N; i++) {
            cin >> a[i];
            maxVal = max(maxVal, a[i]);
            sum += a[i];
        }
        
        int left = maxVal, right = sum, ans = sum;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (judge(N, M, mid, a)) {
                ans = mid;
                right = mid - 1;  // 嘗試更小的最大花費
            } else {
                left = mid + 1;   // 需要增大限制
            }
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵點總結

• 二分查找的是「答案」（最小可能的最大月花費），而非數組下標
• 判定函數貪心地將盡可能多的天數放入當前組
• 時間複雜度：O(N log(sum))，對於 N ≤ 100,000 完全足夠
• 注意使用 long long 防止求和溢出