poj2456
1097 ワード
久しぶりの二分、もうすぐ一年に二分問題をやったことがありません……やはり手描きですね…二分できる範囲を考えてみると、問題木に役に立ちます
/*
* 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;
}