티스토리 뷰

알고리즘 관련/BOJ

BOJ)11973 Angry Cows

JASON 자손9319 2017. 1. 18. 19:36

문제: icpc.me/11973


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11975 Build Gates  (0) 2017.01.18
BOJ)11974 Subsequences Summing to Sevens  (0) 2017.01.18
BOJ)11973 Angry Cows  (0) 2017.01.18
BOJ)10216 Count Circle Groups  (0) 2017.01.17
BOJ)13913 숨바꼭질4  (0) 2017.01.17
BOJ)13549 숨바꼭질3  (0) 2017.01.17
댓글
댓글쓰기 폼