POJ - 3273 Monthly Expense 二分

POJ - 3273 Monthly Expense 二分

題目大意：有一個人財政赤字了，每天都要還一定數量的錢，共要還N天。
現在他要求把這N天還的錢變成M次還掉，也就是說不用每天都還了，可以累積一定的天數再還。
現在要求M次還掉的錢中，錢的最大值達到最小，問這個最小值是多少

解題思路：最大值最小，二分解決
枚舉的最小值是每天還的錢中的最大值，最大值是每天還的錢的總和
因為每次枚舉的錢肯定是大於等於每天還的錢中的最大值的，所以最多可以分成N個集合，然後在算出最小的集合，最小的集合數量就是每一個集合盡量包含更多的天數

#include
#include
#include
using namespace std;
#define maxn 100010
long long num[maxn],Sum, Min;
int N, M;

bool judge(long long mid) {
    int cnt = 1, count;
    long long money = 0;
    for(int i = 0; i < N; i++) {
        money += num[i];
        if(money > mid) {
            money = 0;
            i--;
            cnt++;
        }
    }
    if(cnt <= M)
        return true;
    return false;
}

long long solve() {
    long long l = Min, r = Sum;
    while(l < r) {
        long long mid = (l + r) / 2;
        if(judge(mid)) 
            r = mid - 1;
        else
            l = mid + 1;
    }
    return l;
}

int main() {
    while(scanf("%d%d",&N, &M) != EOF) {
        Sum = 0, Min = -1;
        for(int i = 0; i < N; i++) {
            scanf("%lld", &num[i]);
            Min = max(Min, num[i]);
            Sum += num[i];
        }
        printf("%lld\n",solve());
    }
    return 0;
}