[BaekJoon][2110] 공유기 설치

BAEKJOON ONLINE JUDGE

2110 공유기 설치

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

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int home[200000];
 
int main()
{
    int n, c;
    int start = 1, end, cnt, middle, ans;
    int h;
    int i;
 
    scanf("%d %d", &n, &c);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &home[i]);
    }
 
    sort(home, home + n);
 
    end = home[n - 1] - home[0] + 1;
 
    while (start <= end) {
        middle = (start + end) / 2;
 
        cnt = 1;
        h = home[0]; 
        for (i = 1; i < n && cnt <= c; i++) {
            if (home[i] - h >= middle) {
                cnt++;
                h = home[i];
            }
        }
 
        if (cnt >= c) {
            ans = middle;
            start = middle + 1;
        }
        else end = middle - 1;
    }
 
    printf("%d\n", ans);
 
    return 0;
}