공유기 설치

• 이분탐색 문제에 적응중

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
// 10^9 = 10억
int N, C, ans;
vector<int> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> C;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    /* left초기값이 0이면 mid가 0일경우가 나오기때문에 1로 초기화하자 */
    int left = 1;
    int right = v.back();
    int ans=0;
    while(left <= right)
    {
        int cnt = 1;
        int mid = (left + right) / 2;
        int start = v[0];
        /* 간격이 mid일 때 공유기를 몇개 심을 수 있는지 카운트 */
        for(int i=1;i<v.size();i++)
            if(v[i] - start >= mid) {
                start = v[i];
                cnt++;
            }
        /* 공유기의 거리를 최대로 하는 방향에 = 등호를 붙여서 답을 기억 */
        if(cnt >= C){
            left = mid + 1;
            ans=mid;
        }
        else right = mid - 1;
    }
    cout << ans;
    return 0;
}

• 로직
  • 집 사이간 간격에 따라 심을 수 있는 공유기 수 를 구하고 우리가 세우려는 C개 보다 크거나 같을 때 간격을 늘리면서 결국 C개의 공유기를 심을 수 있는 최대 거리를 구한다

• 이분탐색 구현시 주의
  • 답을 기억하는 =(등호)가 붙는 방향은 앞으로 답이 될 수 있는 가능성이 있는 쪽에 붙여주어야 한다
  • left의 초기값을 0으로 하면 나누는 값인 mid가 0이될 수 있으니 1로 초기화하자