POJ - 2456 Aggressive cows 二分

POJ - 2456 Aggressive cows 二分

題目大意：有N個牛捨在同一條直線上，每個牛捨都有相應的坐標
現在有C頭牛，要求放在這牛捨中，使得相鄰兩頭牛之間的距離的最小值達到最大

解題思路：直接二分距離，然後再進行判斷
這題得反省一下了：因為我把cur重復定義了，所以一直找不到錯誤，標記一下。。。

#include
#include
#include
using namespace std;
#define maxn 100010
int pos[maxn];
int n, c;

int find(int s, int e, int dis) { 
    int l = s, r = e;
    while(l < r) {
        int mid = (l + r) / 2;
        if(pos[mid] >= dis) 
            r = mid;
        else 
            l = mid + 1;
    }
    return l;
}

bool judge(int mid) {
    int dis = pos[0], cur = 1;
    for(int i = 1; i < c; i++) {
        dis += mid;
        if(dis > pos[n - 1])
            return false;
        cur = find(cur, n - 1, dis);
//      int cur = lower_bound(pos, pos + n, dis) - pos;
        dis = pos[cur];
    }
    return true;
}

int solve() {
    int l = 0, r = pos[n - 1];
    while(l <= r) {
        int mid = (l + r) / 2;
        if(judge(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l - 1;
}

void init() {
    for(int i = 0; i < n; i++)
        scanf("%d", &pos[i]);

    sort(pos, pos + n);
}

int main() {
    while(scanf("%d%d", &n, &c) != EOF) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}