2805번: 나무 자르기

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


$O(n\lg h)$

자르는 높이를 기준으로 파라매트릭 서치를 한다.

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