読者です 読者をやめる 読者になる 読者になる

PKU3258 River Hopscotch

蟻本の練習問題。
岩の位置をソートして二分探索

#include <cstdio>
#include <algorithm>
using namespace std;

int l, m, n;
int rock[50000];

bool C(int d){
    int last = 0;
    while(rock[last] < d){
	last++;
	if(last == n) return false;
    }
    for(int i = 1; i < n - m; i++){
	int crt = last + 1;
	while(crt < n && rock[crt] - rock[last] < d){
	    crt++;
	}
	if(crt == n) return false;
	if(l - rock[crt] < d) return false;
	last = crt;
    }
    return true;
}

int main(){
    scanf("%d %d %d", &l, &n, &m);
    for(int i = 0; i < n; i++){
	scanf("%d", &rock[i]);
    }
    sort(rock, rock + n);
    int lb = 0; int ub = l + 1;
    while(ub - lb > 1){
	int mid = (ub + lb) / 2;
	if(C(mid)) lb = mid;
	else ub = mid;
    }
    printf("%d\n", lb);
    return 0;
}