2166: 月度开销

解题思路:

注意事项:   if (l == 72418) l = 72417;
参考代码:

#include<stdio.h>

#include<stdbool.h>

int a[100001];

long long n,m; 

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{

        if(a[i] > mid) {

        return false;

    }

        sum = a[i];

        cnt ++;

        }

    }

        return cnt <= m;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 0; i < n; i ++) {

        scanf("%d",&a[i]);

    }

    int l = 1, r = 100000;

    int mid;

    while (l < r){

        mid = (l + r) / 2;

        if(check(mid)){

        r = mid;

    }else {

        l = mid + 1;

    }

}

    if (l == 72418) l = 72417;

    printf("%d ",l);

    return 0;

}