BOJ)11973 Angry Cows

문제: icpc.me/11973

Angry Cow를 x위치에 던지면 [x-R,x+R]위치의 건초가 모두 파괴된다.

N개의 건초더미의 위치가 주어질 때 K마리의 Angry Cow를 던져서 모든 건초를 파괴하려할 때 R의 최솟값을 출력하는 문제이다.

우리는 건초더미들의 위치를 구간으로 생각하여 한 Angry Cow가 구간 2*R을 파괴할 때 K마리의 Angry Cow가 전체 구간을 다 파괴할 수 있는지를 확인하여 R의 최솟값을 구해야한다.

R의 최솟값은 이분탐색을 통하여 구할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, k, a[50010], lo, hi, b[50010];
int main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);
    for (int i = 1; i < n; i++)
        b[i] = a[i] - a[i - 1];
    hi = 100000000000;
    while (lo < hi) {
        ll mid = (lo + hi) >> 1;
        ll v = mid;
        ll c = 1;
        for (int i = 1; i < n; i++) {
            if (v >= b[i]) 
                v -= b[i];
            else {
                v = mid;
                c++;
            }
        }
        if (c <= k)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%lld\n", (lo + 1) / 2);
    return 0;
}