2110번-공유기설치

문제

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

2110번: 공유기 설치

---

접근방법

일반적인 이분탐색 문제와 유사하지만 기준으로 정한 거리(mid)값의 변화를 측정하기 위한 이전 인덱스를 변경하는 35번째 줄에서 약간의 구현력이 필요했던 문제였습니다. 그 외에는 일반적인 이분탐색 문제였습니다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 2e5 + 1;
ll arr[MAX];
int n, c;
int main(void)
{
    fastio;
    cin >> n >> c;
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    sort(arr, arr + n);
 
    ll left = 1;
    ll right = arr[n - 1];
    ll ans = -1;
 
    while (left <= right)
    {
        ll mid = (left + right) / 2;
        ll cnt = 1, beforeIdx = 0;
 
        for (int i = 1; i < n; i++)
        {
            if (arr[i] - arr[beforeIdx] >= mid)
            {
                beforeIdx = i;
                cnt++;
            }
        }
 
        if (cnt >= c)
        {
            left = mid + 1;
            ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans << "\n";
}