二分之「火車站台連鎖店」
二分是一種快速的查找方式，時間複雜度極低，為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; }
