BAEKJOON 2110 - 공유기 설치

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

랜선 자르기와 비슷한 방법으로 풀 수 있는 문제입니다. 공유기를 원래 설치하려는 개수와 같거나 더 많이 설치할 수 있는 조건하에서 최대 간격을 구해야 되는 문제입니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll getRouterNumber(const int* numbers, int minLength, int n)
{
    ll ret = 1;
    int lastPos = numbers[0];
    for (int i = 1; i < n; i++)
    {
        if (numbers[i] >= lastPos + minLength)
        {
            ret++;
            lastPos = numbers[i];
        }
    }
    return ret;
}
 
ll binarySearch(const int* numbers, ll low, ll high, ll needNumber, ll n)
{
    ll ret = 0;
    while (low <= high)
    {
        ll mid = (low + high) / 2;
        ll routerNumber = getRouterNumber(numbers, mid, n);
        if (needNumber > routerNumber)
        {
            high = mid - 1;
        }
        else
        {
            ret = max(ret, mid);
            low = mid + 1;
        }
    }
    return ret;
}
 
int main()
{
    int n, c, highest;
    highest = 0;
    scanf("%d %d", &n, &c);
    int* numbers = new int[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &numbers[i]);
        highest = max(highest, numbers[i]);
    }
    sort(numbers, numbers + n);
 
    printf("%d\n", binarySearch(numbers, 0, highest, c, n));
 
    delete[] numbers;
    return 0;
}