[2110] 공유기 설치

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

이 문제는 저는 개인적으로 꽤 어려웠는데요....

이분 탐색으로 풀 수 있는 문제입니다..

파라메트릭 서치(?)라고.. K번째 수와 마찬가지로 이분 탐색의 응용인 문제인데

집의 수와 공유기의 수 그리고 집의 좌표를 줍니다.

최대한 넓게 넓게 설치해서 인풋으로 요구하는 공유기의 수를 만들어야 하는데..

여기서 어떻게 이분탐색을 하느냐에 대해서 엄청나게 고민했습니다.

결론부터 말하자면! 우리는 거리를 가지고 이분탐색을 해야합니다.

예를 들어 거리를 10으로 첫 시작을 했다면 10간격으로 설치를 해보고 공유기가 더 많이 필요하면 간격을 늘리고

공유기가 덜 설치되었으면 거리를 줄이는 방식으로 이분탐색을 진행하면 됩니다.

#include <cstdio>
#include <algorithm>
#define MAX_SIZE 200000
 
int pos[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    for(int i = 0; i < n; i++) scanf("%d", pos + i);
 
    std::sort(pos, pos + n);
 
    int left = 1, right = pos[n - 1] - pos[0];
    int ret;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int cnt = 1;
        int start = pos[0];
 
        for(int i = 1; i < n; i++)
        {
            if(pos[i] - start >= mid)
            {
                cnt++;
                start = pos[i];
            }
        }
 
        if(cnt >= c)
        {
            ret = mid;
            left = mid + 1;
        }
        else right = mid - 1;
 
    }
 
    printf("%d\n", ret);
 
 
    return 0;
}