POJ 3273: Monthly Expense

概要

要素数Nの数列{a_i}が与えられる．この数列をM個の連続した部分に分け，各部分の要素の合計の最大値を最小化したい．

解法

合計の最大値に対して二分探索を行う．
下限の初期化を間違っていたせいか，WA出した．

あと，最近気が付いたんだけど，二分探索の書き方が蟻本と違う．．．

int N, M;
int a[100010];
int C(int d){
    int cnt = 1, sum = 0;
    for(int i = 0; i < N; ++i){
        if(sum + a[i] > d){
            ++cnt;
            sum = 0;
        }
        sum += a[i];
    }
    return cnt;
}
int main(){
    scanf("%d%d", &N, &M);
    int l = 0, u = 1000000000;
    for(int i = 0; i < N; ++i){
        scanf("%d", &a[i]);
        l = max(l, a[i]);
    }
    int res = -1;
    while(l <= u){
        int mid = (l + u) / 2;
        if(C(mid) <= M){
            res = mid;
            u = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}