2110번_공유기 설치_BOJ

문제 링크

2110번 공유기 설치 : https://www.acmicpc.net/problem/2110

문제 설명 및 해결 아이디어

좌표의 범위가 최대 1,000,000,000이여서 시간초과가 난다.

그래서 Parametric Search로 해결할 수 있다.

mid값을 간격으로 설정한다.

설치한 공유기 개수가 주어진 공유기 개수 C보다 크거나 같을 경우, mid를 크게하여(간격을 크게하여) 공유기 개수를 줄일 수 있다.

반대의 경우, mid를 작게하여 공유기 개수를 늘릴 수 있다. 

코드

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long int
#define MAX_S 200001
ll n, c, res;
ll land[MAX_S];
 
void func() {
    ll left = 1, right = land[n - 1] - land[0] + 1;
    ll cnt, gap;
    while (left <= right) {
        ll mid = (left + right) / 2;
        cnt = 1;
        gap = land[0];
        for (int i = 1; i < n; ++i) {
            if (land[i] - gap >= mid) {
                gap = land[i];
                cnt++;
            }
        }
 
        if (cnt >= c) {
            left = mid + 1;
            res = max(res, mid);
        }
        else {
            right = mid - 1;
        }
    }
 
}
int main() {
    scanf("%lld %lld", &n, &c);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &land[i]);
    sort(land, land + n);
 
    res = -987654321LL;
    func();
    printf("%lld\n", res);
 
    return 0;
}