原题
问题
给出n个位置(数轴上的坐标值),从中选出k个,让这k个位置相邻两个之间的距离(相邻位置坐标的差值)尽可能的大(尽可能大的意思是这k-1个距离的最小值尽量大)。输出这个最大的最小值。
样例解释
选位置:1 5 9。
输入
第一行:2个数n和k(2 <= n <= 100000, 2 <= k <= 10000, k <= n)
后面n行:每行一个数Pi,表示具体位置(0 <= Pi <= 10^9),位置是无序的。
输出
输出一个数,对应最大的距离。
输入样例 5 3 1 3 5 7 9 输出样例 4
题解
这个题目是一个经典的二分答案题。(当看到题目中有问最大的最小值,一般就是二分答案题目了)
二分答案首先要明白我们要二分的数据,这里,我们可以选择二分这个最大距离。
知道了要二分的数据,就可以写check函数了,我们现在main函数中对数据进行排序,从头开始,每隔大于等于mid距离就统计一次,到最后看一看是否满足k个位置,如果满足,就把mid值调大(因为要求最大的最小值),如果不满足,就调小。
bingo,问题解决。
二分答案有一个特点,就是思路简单,代码难写,正和dp相反。
下面我就先放出核心代码(check函数)
bool check(int x) { int cnt=1,t=a[1]; for(int i=2;i<=n;i++) { if(a[i]-t>=x) { cnt++; t=a[i]; } } return cnt>=k; }
其实看一看也没有多难。
下面是全部代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define inf 100000000 7 using namespace std; 8 int a[100000],n,k; 9 bool check(int x) 10 { 11 int cnt=1,t=a[1]; 12 for(int i=2;i<=n;i++) 13 { 14 if(a[i]-t>=x) 15 { 16 cnt++; 17 t=a[i]; 18 } 19 } 20 return cnt>=k; 21 } 22 int main() 23 { 24 cin>>n>>k; 25 for(int i=1;i<=n;i++) 26 { 27 cin>>a[i]; 28 } 29 int l,r,m; 30 sort(a+1,a+1+n); 31 l=0,r=1e9+1; 32 while(l<r-1) 33 { 34 m=(l+r)/2; 35 if(check(m)) 36 l=m; 37 else 38 r=m; 39 } 40 cout<<l; 41 return 0; 42 }