USACO 2016 January Contest, Silver Problem 1. Angry Cows

http://www.usaco.org/index.php?page=viewproblem2&cpid=594

一開始寫這題的時候，也不知道要怎麼寫。

後來仔細想想，似乎有單調性。於是乎，就可以寫二分搜了。

Tip : Binary Search

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

const int MAX_N = 50002;
int loc[MAX_N];
int n;

int K(int r) {
    int ret=0;
    int id=0;
    int to=-1;
    while (id<n) {
        if (loc[id]>to) {
            to = loc[id]+2*r;
            ret++;
            
        }
        else {
            id++;
        }
    }
    return ret;
}

int main () {
    freopen("angry.in","r",stdin);
    freopen("angry.out","w",stdout);
    int k;
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int x=0;n>x;x++) scanf("%d",&loc[x]);
        sort(loc,loc+n);
        int L=0,R=1000000002;  //L 是 答案 
        while (R-L!=1) {
            int mid = (L+R) >> 1;
            if (K(mid)<=k) R = mid;
            else L = mid;
        }
        printf("%d\n",R);
    }
}