Algoogle

Algorithm for Programming Contest

PKU 2456 Aggressive cows

Category: PKU Tag: binary-search

Aggressive cows

問題概要


解法


最大の最小化なので2分探索. xはソートしておく. その距離でできるかは左から条件を満たすように詰めて置いてみればよい.

コード


(2456.cpp) download
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
34
35
#include <algorithm>
#include <cstdio>

using namespace std;

const int inf = int(1e9);

int N, C, x[100010];

bool can(int d){
    int prev = 0;
    for(int i = 1; i < C; i++){
        int pos = prev+1;
        while(pos < N && x[pos] - x[prev] < d) pos++;
        if(pos == N) return 0;
        prev = pos;
    }
    return 1;
}

int main(){
    scanf("%d%d", &N, &C);
    for(int i = 0; i < N; i++)
        scanf("%d", x+i);
    sort(x, x+N);

    int lb = -1, ub = inf+1;
    while(ub - lb > 1){
        int mid = (lb + ub) / 2;
        if(can(mid)) lb = mid;
        else ub = mid;
    }
    printf("%d\n", lb);
    return 0;
}

Comments