POJ 3273 Monthly Expense：二分答案檢查分組可行性

POJ 3273 Monthly Expense：二分答案檢查分組可行性

將 N 個正整數連續分成 M 組，使各組和的最大值最小化。經典「二分答案 + 貪心檢查」模型。

二分邊界

• 下界 low = max(所有元素) (至少能容納最大單元素)。
• 上界 high = sum(所有元素) (單組包含所有)。

檢查函數 check(mid)

模擬分組：累加元素，超過 mid 則新開一組。統計所需組數 cnt。若 cnt ≤ M 則 mid 可行 (可再嘗試更小)；否則 mid 過小。

C++ 代碼

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

int a[100010];
int N, M;

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

int main() {
    while (cin >> N >> M) {
        int low = 0, high = 0;
        for (int i = 1; i <= N; i++) {
            cin >> 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;
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度

O(N log Sum)，N ≤ 10^5，Sum ≤ 10^9，極快。