1654번: 랜선 자르기

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


$O(n\lg l)$

랜선의 길이를 기준으로 파라매트릭 서치를 한다.

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