13397번: 구간 나누기 2

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


$O(n\lg c)$

차이를 기준으로 파라매트릭 서치를 한다.
최대 차이 x가 가능한지 판단하기 위해 주어진 배열 {ai}를 앞에서부터 x가 넘는 시점마다 구간을 나눈다.
나눈 구간 개수가 m이하면 가능하다.

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