POJ 2456 Aggressive cows
問題
http://poj.org/problem?id=2456
解法
距離で二分探索。はじめ再帰で書いたが終了条件がよくわからなくてWAになったのでループ回した。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; int N, C; int a[MAX_N]; bool c(int d){ //printf("check %d\n", d); int p = a[0], cow = 1; for(int i = 1; i < N; i++){ if(a[i] - p >= d){ cow++; p = a[i]; if(cow == C) break; } } return (cow == C); } int solve(){ int l = 1, h = 1000000010; for(int i = 0; i < 100; i++){ int m = (l + h) / 2; if(c(m)) l = m; else h = m; } return l; } int main(){ scanf("%d %d", &N, &C); for(int i = 0; i < N; i++) scanf("%d", &a[i]); sort(a, a + N); printf("%d\n", solve()); return 0; }