白準2110ルータのインストール

質問する

[2110題リンク]

に答える

ルータ間の「間隔」を二分探索として探します.
たとえば、間隔が3の場合、最初の家にルータをインストールし、2番目の家から前のルータとの間隔が3より大きいかどうかを確認します.間隔が3より大きい場合は、ルータをインストールし、次の家をブラウズし、間隔の計算を繰り返します.
すべての家屋を検査する場合、設置されたルータがcより多い場合は間隔が増加し(right = gap - 1)、c以下の場合は間隔が減少する(left = gap + 1)

ソースコード

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, c;
    cin >> n >> c;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());

    int left = 1;
    int right = vec[n - 1] - vec[0];
    int ans = 0;

    while (left <= right) {
        int gap = (left + right) / 2;
        int cnt = 1;
        int bef = vec[0];
        for (int i = 1; i < n; i++) {
            if (vec[i] - bef >= gap) {
                cnt++;
                bef = vec[i];
            }
        }
        if (cnt >= c) {
            ans = gap;
            left = gap + 1;
        } else {
            right = gap - 1;
        }
    }

    cout << ans;

    return 0;
}

このナビゲーションコードのフレームワークを暗記しましょう.

 while (left <= right) {
        int mid = (left + right) / 2;
        
        // mid 값으로 계산했을 때 조건을 만족하는 경우가 얼마나 되는지 구한다. 
        // 이 값을 cnt라고 하고, 최종적으로 만족해야 하는 값은 c라면
        if ( cnt >= c) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }