백준 11973 Angry Cows (USACO January 2016 Silver 1번)

문제 링크: https://www.acmicpc.net/problem/11973

11973번: Angry Cows (Silver)

Binary Search

폭발 반경 R을 기준으로 모든 hay bales 를 다 터뜨리기 위해 발사해야 할 소의 갯수가 K보다 작거나 같으면 hi를 낮추고, K보다 크면 lo를 높이면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int N, K, pos[50001], ans;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> pos[i];
    sort(pos, pos + N);
 
    int lo = 0, hi = 1e9;
    while(lo <= hi) {
        int mid = (lo + hi) / 2;
        int cnt = 1;
        int idx = 0;
        for(int i = 0; i < N; i++) {
            if(pos[i] - pos[idx] <= 2 * mid) continue;
            else {
                cnt++;
                idx = i;
            }
        }
        if(cnt <= K) {
            ans = mid;
            hi = mid - 1;
        }
        else
            lo = mid + 1;
    }
 
    cout << ans << '\n';
    return 0;
}