二分之“火车站台连锁店”
二分是一种快速的查找方式，时间复杂度极低，为log2（r-l）（r为右边界，l为左边界,（r-l）为区间长度，log2(r-l)一般不超过100)，非常实用，下面这道题便是一道经典的二分题；
火车站台连锁店
描述
蒜头君建立了一家火车站台连锁店，要在一条铁路线的所有车站里，选择一部分车站开办连锁店，销售各种口味的大蒜。
铁路线上有 n 个车站，假设这条铁路线是一条直线，其中每个站点的坐标为 x1,x2,…,xn；
蒜头君一共要开办 m 个连锁店，并且不希望连锁店离得太近，以使得整体的收益最大化。他希望他的连锁店之间的最近距离尽可能大，你能帮他算出这个最大的最近距离吗？
输入
第一行输入用空格分隔的两个整数 n,m(2 ≤ n ≤ 105,2 ≤ m ≤ n)分别表示车站数量和连锁店数量。
接下来一共 n 行，每行一个整数 x_i（0 ≤ xi ≤ 109），表示车站的坐标。
输出
输出一行整数，表示最大的最近距离。
输入样例 1
6 3
1
3
5
2
7
9
输出样例 1
4
输入样例 2
5 4
5
7
10
28
9
输出样例 2
2
提示
样例 2 说明
一共有 5 种选择方案：
5 7 9 10：最近距离为 min(7-5,9-7,10-9)=1
5 7 9 28：最近距离为 min(7-5,9-7,28-9)=2
5 7 10 28：最近距离为 min(7-5,10-7,28-10)=2
7 9 10 28：最近距离为 min(9-7,10-9,28-10)=1
5 9 10 28：最近距离为 min(9-5,10-9,28-10)=1
因此，最大的最近距离为 2。
这道题，乍一眼，我的第一感觉是用dfs去做，但又转念一想，这个的数据范围很大，很可能会超时，于是，只能换种思路。
我又想到了dp去做这道题，但我实在是想不到怎么用dp写，只能放弃，用二分去做；
首先，我们先对数组进行排序，为二分做准备：
sort(a+1,a+1+n);//排序，因为二分必须需要完全的升序或降序排列
然后定义左边界，右边界，并为其赋值
int l=0,r=a[n]-a[1];//给左边界，右边界赋初值
接下来就是二分操作，但其实这不是真正的核心，真正的核心操作在后面：
while(r-l>1)//二分 { int mid=(l+r)/2; if(ok(mid)) l=mid; else r=mid; }
这是二分的基础模板，可以进行记忆；
然后便是核心代码——ok函数：
bool ok(int x){ int tot=1;//表示选择了的个数 int last=1; for(int i=1;i<=n;i++)//查找 { while(a[i]-a[last]<x)//如果比我们约定的最小值小，就i++ { i++; if(i>n) return tot>=m; // 如果多出了车站数，就return; } last=i; tot++; } return tot>=m; }
最后，补充上基础结构和变量的定义，这道题就做出来了
#include<bits/stdc++.h> using namespace std; int n,m; int a[100010]; bool ok(int x){ int tot=1;//表示选择了的个数 int last=1; for(int i=1;i<=n;i++)//查找 { while(a[i]-a[last]<x)//如果比我们约定的最小值小，就i++ { i++; if(i>n) return tot>=m; // 如果多出了车站数，就return; } last=i; tot++; } return tot>=m; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n);//排序，因为二分必须需要完全的升序或降序排列 int l=0,r=a[n]-a[1];//给左边界，右边界赋初值 while(r-l>1)//二分 { int mid=(l+r)/2; if(ok(mid)) l=mid; else r=mid; } if(!ok(r)) r=l;//再检查一次，检查r是否正确答案 cout<<r; return 0; }
