Angry Cows

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

11973번: Angry Cows (Silver)

이 문제는 parametric search + greedy 문제입니다.

greedy는 증명이 대체로 어렵습니다. 그냥 감으로 이러면 되겠군.. 

이 문제의 경우 greedy 증명이 크게 어렵지 않아서 다행이네요.

lower_bound / upper_bound 함수 사용이 익숙하지 않다면, 꼭 공부합시다! (사실 내가 익숙하지 않음..ㅠㅠ)

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, k;
 
bool check(ll r, vector<int> &v) {                        // 사실상 main안에 있는 이분탐색보다 이 check 함수가 주인공이다.
    int idx = 0;                                                // 어떻게 하면 커버해줄 수 있는지 없는지를 효율적으로 구현해 판단해야한다.
    r <<= 1;                                                   // 그냥 while 문으로 아주 naive하게 구현해 줄 수도 있었지만, upper_bound를 알고
    for (int i = 0; i < k; i++) {                             // 있으니 써주는게 좋겠다.
        idx = upper_bound(v.begin(), v.end(), v[idx] + r) - v.begin();    // 커버는 greedy하게 하면된다. 맨 왼쪽 헛간부터 지름만큼 계속 커버를 시도한다.
        if (idx == v.size()) return true;                    // 주어진 기회 k안에 끝까지 다 커버했으니 true를 반환한다.
    }
    return false;                                               // 기회 k안에 커버를 못했으니 false를 반환한다.
}
 
 
int main() {
    FastIO;
 
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
 
    sort(v.begin(), v.end());             // 소를 던졌을 때 헛간이 어디가 부서지는지 확인하기 위해 정렬을 해준다.
    int l = -1, r = 1000000000 / 2 + 1;    // 이 초기값 설정이 매우 중요하다. 답이 될 수 있는 모든 구간을 포함하였는지 정확히 꼼꼼히 확인해준다.
    while (l + 1 < r) {
        int m = (l + r) >> 1;
        if (check(m, v)) r = m;
        else l = m;
    }
    cout << r;
}