题目描述
有N个整数，值从0到1000000000，2<=N<=100000。要从中选出C个数（2<=C<=N），使得任意两个数差的绝对值的最小值尽可能大，求这个最大值。
输入
第一行是N和C。
接下来的N行，每行一个整数。
输出
一个整数，表示两两最小差距的最大值。
样例输入
第一行是N和C。
接下来的N行，每行一个整数。
样例输出
3
提示
选择1、4和8
代码
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=(j);i<=(k);++i) #define per(i,j,k) for(register int i=(j);i>=(k);--i) using namespace std; template<class T> inline void read(T &x) { x=0; register char c=getchar(); register bool f=0; while(!isdigit(c))f^=c=='-',c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x; } const int N=100001; int f[N],n,c,a[N],l=1,r,ans,tmp,mid; inline bool check(register int mid) { register int t=a[1],sum=1; rep(i,2,n) if(abs(a[i]-t)>=mid) sum++,t=a[i]; return sum>=c; } int main() { read(n),read(c); rep(i,1,n) read(a[i]); sort(a+1,a+1+n); r=a[n]-a[1]; if(n%2==1) tmp=max(a[(n+1)/2]-a[(n+1)/2-1],a[(n+1)/2+1]-a[(n+1)/2]); else tmp=a[n/2+1]-a[n/2]; tmp=max(tmp,100); while(l+tmp<=r) { mid=(l+r)/2; if(check(mid)==true) l=mid+1; else r=mid-1; } per(i,r,l) if(check(i)==true) { printf("%d",i); return 0; } }