1508번: 레이스

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


$O(k\lg n)$

파라매트릭 서치를 이용한다.

#include<cstdio>
int n, m, k, a[50], c, t;
bool f(int x) {
    t = -n;
    for (int i = c = 0; i < k; i++) if (a[i] - t >= x) t = a[i], c++;
    return c >= m;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++) scanf("%d", a + i);
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        f(mid) ? l = mid + 1 : r = mid - 1;
    }
    t = -n;
    for (int i = c = 0; i < k; i++) {
        printf("%d", a[i] - t >= r&&c < m);
        if (a[i] - t >= r) t = a[i], c++;
    }
    return 0;
}