공유기 설치 C++ - 백준 2110

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

파라메트릭 서치 문제.

이 문제는 다른 파라메트릭 서치 문제들과는 다르게

조금 꼬인 느낌의 문제였다.

문제 접근

인접 공유기의 거리를 최대로 하려면 일단 두 공유기가 멀리 있어야 하는데,

이는 다른 공유기들에게도 영향을 미치므로 최대한 인접 공유기들의

간격을 비슷비슷하게 배치해야 한다는 것을 알 수 있다.

이를 이분탐색을 사용하면서 어떻게 구현해야 할까?

인접 공유기 간 거리는 정해져있다. 하지만 이분탐색을 하게 되면

이분탐색 한 값이 인접 공유기 간 거리와 일치하지 않을 수도 있다.

이 부분에서 조금 헤맸는데,

생각해보니까 인접한 공유기 간 거리의 최소값을 최대로 해야 하기에

이분탐색한 값보다 같거나 크면, 그 값을 사용하면 되겠다는 생각이 들었다.

따라서 이분탐색 한 값보다 같거나 크면 공유기를 설치한다.

공유기 개수가 c개가 아니면 l,r를 다른 값으로 적절히 바꾸어 준다.

정말 중요한 이분탐색 결과에서의 답

이분탐색을 진행할 때 $l<=r$로 진행했다.

따라서 이분탐색 종료시에는 $l$이 $r+1$로 이동하거나

$r$이 $l-1$로 이동하게 되는데

$l$이 $r+1$로 이동하는 경우는 $l,r$에서 가능했기에 다음 $r+1$를 보는 경우인데,

진행된 이분탐색에서는 $r$을 $mid-1$로 조정했기 때문에,

답은 $r$이 된다.

$r$이 $l-1$로 이동하는 경우는 $l,r$에서 불가능했을 때에 이동하는데,

$l$에서는 불가능하기 때문에 이때도

$r$이 답이 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,c;
    cin >> n >> c;
    vector<int> h(n);
    for(int i=0;i<n;i++) cin >> h[i];
    sort(h.begin(),h.end());
    int l=1,r=h[n-1]-h[0],mid;
    while(l<=r){
        mid=(l+r)/2;
        int cnt=1,cur=h[0];
        for(int i=1;i<n;i++) if(h[i]-cur>=mid){cnt++; cur=h[i];}
        if(cnt>=c) l=mid+1;
        else r=mid-1;
    }
    cout << r;
    return 0;
}