2792번: 보석 상자

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


$O(m\lg a)$

질투심을 가지고 파라매트릭 서치를 해본다.

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