poj2456

久しぶりの二分、もうすぐ一年に二分問題をやったことがありません……やはり手描きですね…二分できる範囲を考えてみると、問題木に役に立ちます

/*
 * poj2456.cpp
 *
 *  Created on: 2010-8-12
 *      Author: friendy
 */

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

int n,num[100001],c;

int binary(int mid){
	int i,pos,sum;
	pos=1;
	for(i=1;i<c;i++){
		sum=0;
		while(pos<n&&sum<mid){
			sum+=(num[pos]-num[pos-1]);
			pos++;
		}
		if(sum<mid)
			return 0;
	}
	return 1;
}

int main(){
	int i;
	scanf("%d%d",&n,&c);
	for(i=0;i<n;i++){
		scanf("%d",&num[i]);
	}
	sort(num,num+n);
	int l=0;
	int r=(num[n-1]-num[0])/(c-1);
	while(l<=r){
		int mid=(l+r)>>1;
		if(binary(mid))
			l=mid+1;
		else
			r=mid-1;
	}
	printf("%d
",r);
	return 0;
}