구간 나누기 2 (백준 13397)

안녕하세요. 오늘은 구간을 나눌 거예요.

문제

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

아이디어

cal(x)를 구간의 점수가 모두 x이하가 되게 하도록 구간을 나눌때 구간의 개수의 최솟값이라고 합시다. 이 값이 M이하이면 x는 가능, 아니면 불가능입니다. 이걸 가지고 파라메트릭 서치를 하면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll N, arr[5050] = { 0 };
ll cal(ll x)
{
    ll mn = 2e9, mx = -2e9, cnt = 0;
    for (ll i = 1; i <= N; i++)
    {
        mx = max(mx, arr[i]);
        mn = min(mn, arr[i]);
        if (mx - mn > x)
        {
            cnt++;
            mx = mn = arr[i];
        }
    }
    cnt++;
    return cnt;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, left, mid, right, ans = 100000;
    cin >> N >> M;
    for (ll i = 1; i <= N; i++) cin >> arr[i];

    left = 0; right = 100000;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (cal(mid) <= M)
        {
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << ans;
}

감사합니다!