2343번: 기타 레슨

https://www.acmicpc.net/problem/2343


$O(n\lg t)$

블루레이의 길이를 기준으로 파라매트릭 서치를 한다.

#include<cstdio>
int n, m, a[100000], low, up = 1e9, mid;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        if (a[i] > low) low = a[i];
    }
    while (low <= up) {
        mid = (low + up) / 2;
        int s = 0, c = 1;
        for (int i = 0; i < n; i++) {
            if (s + a[i] > mid) s = 0, c++;
            s += a[i];
        }
        c > m ? low = mid + 1 : up = mid - 1;
    }
    printf("%d", low);
    return 0;
}