做不對的二分

二分這個知識點，我好像在高中就有在數學課本中接觸，到了編程上才知道，二分是真的難，
二分殺我！！！
首先呢，說一說我對做二分題的理解
二分題先要理解題意然后去套模板就可以了，去理解是找>=x的最小值還是<=x的最大值，下面是兩個模板，
>=x的最小值模板

while(l < r){
	//mid的型別可以根據具體來變
	int mid = l + r >> 1;
	if(check(mid)) r = mid;
	else l = mid + 1;
}

<=x的最大值模板

while(l < r){
	//mid的型別可以根據具體來變
	int mid = l + r + 1 >> 1;
	if(check(mid)) l = mid;
	else r = mid - 1;
}

以上的兩個模板，在我做題的程序中是沒有問題的（可能因為我比較菜），不過既然這個模板可以存下來，就證明它是經過很多人試驗并補全的，
當然我們不能一味的死套模板，需要根據實際情況加以變通（目前我還不會，沒有遇到）

小數二分我認為較為簡單，模板如下

while(r - l > eps){//此處的eps需要自己定義精度
	if(check(mid)) l = mid;
	else r = mid;
}

個人認為，無論是整數二分還是小數二分，關鍵在于用對模板和寫好check函式，當然l，r的值也需要注意（后邊有例題會專門提到）

首先我們看最經典的跳石頭問題

題目
這項比賽將在一條筆直的河道中進行，河道中分布著一些巨大巖石，組委會已經選擇好了兩塊巖石作為比賽起點和終點，在起點和終點之間，有 N塊巖石（不含起點和終點的巖石），在比賽程序中，選手們將從起點出發，每一步跳向相鄰的巖石，直至到達終點，

為了提高比賽難度，組委會計劃移走一些巖石，使得選手們在比賽程序中的最短跳躍距離盡可能長，由于預算限制，組委會至多從起點和終點之間移走 M 塊巖石（不能移走起點和終點的巖石），

輸入
第一行包含三個整數 L,N,ML,N,M，分別表示起點到終點的距離，起點和終點之間的巖石數，以及組委會至多移走的巖石數，保證 L≥1 且 N≥M≥0，

接下來 N 行，每行一個整數，第 i 行的整數 Di( 0 < Di <L) 表示第 i 塊巖石與起點的距離，這些巖石按與起點距離從小到大的順序給出，且不會有兩個巖石出現在同一個位置，

輸出
一個整數，即最短跳躍距離的最大值
輸入例子
25 5 2
2
11
14
17
21
輸出
4
首先我們理解題意，要找跳躍距離的最大值
所以，我們要使用<=x的模板

int l = 0,r = L;//左邊界l為0，右邊界r為起點石頭到終點石頭的距離
while(l < r){
	int mid = l + r + 1>> 1;
	if(check(mid)) l = mid;//如果treu就將左邊界往右靠
	else r = mid - 1;
}

模板用對后，我們就需要根據題意去寫check函式

bool check(int x){
	int now = 0;//now為現在所處石頭的坐標，剛開始設為0
	int count = 0;//需要移走的石頭數目
	for(int i = 1;i <= n + 1;i++){
		if(a[i] - a[now] < x) count++;/*如果面前的石頭到現在所處
石頭的距離小于x，我們就需要把面前的石頭移走*/
		else now = i;//否則就跳過去然后把現在所處的石頭更新
	}
	if(count <= m) return true;//如果需要移走的石頭數<=規定的回傳true
	else return false;//否則回傳false
}

整體代碼如下

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 500010; 

int n,m;//n為起點到終點的巖石數，m為組委會  至  多  移走的巖石數，
int L,a[N]; 


bool check(int x){
	int now = 0;
	int count = 0;
	for(int i = 1;i <= n + 1;i++){
		if(a[i] - a[now] < x) count++;
		else now = i;
	}
	if(count <= m) return true;
	else return false;
}

int main(){
	scanf("%d%d%d",&L,&n,&m);
	
	a[0] = 0;a[n + 1] = L;//0為起點石頭，n+1為終點石頭
	for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
	
	int l = 0,r = L;
	while(l < r){
		int mid = l + r + 1>> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d",l);
	return 0;
}

其實按照這個思路來 跳石頭還蠻簡單的哇

接下來看一個需要對l和r的值特別注意的題，

題目
對于給定的一個長度為N的正整數數列A1～AN ，現要將其分成 M（M≤N）段，并要求每段連續，且每段和的最大值最小，

關于最大值最小：

例如一數列4 2 4 5 1 要分成 3 段，

將其如下分段：
[4 2][4 5][1]

第一段和為 6，第 2 段和為 9，第 3 段和為 1，和最大值為 9，

將其如下分段：
[4][2 4][5 1]

第一段和為 4，第 2 段和為 6，第 3 段和為 6，和最大值為 6，

并且無論如何分段，最大值不會小于 6，

所以可以得到要將數列4 2 4 5 1 要分成 3 段，每段和的最大值最小為 6，

輸入
第 1 行包含兩個正整數 N,M，

第 2行包含 N 個空格隔開的非負整數 A_i，含義如題目所述，

輸出
一個正整數，即每段和最大值最小為多少，
輸入例子
5 3
4 2 4 5 1
輸出
6

同樣先理解題意，找最大值最小為多少我們就得用>=x的模板

while(l < r){
	int mid = l + r >> 1;
	if(check(mid)) r = mid;
	else l = mid + 1;
} 

但是我們要注意l,r的取值

for(int i = 0;i < n;i ++){
	scanf("%d",&a[i]);
	r += a[i]; //r取了和
	if(a[i] > l) l = a[i];	//l取了最大值
}

我們可以根據題意知道二分的范圍，左邊界應該不小于數列分段單個最大值，右邊界不大于總和，
當l取0的時候是有一個測驗點會wa的,我也不知道為啥，根據討論區大佬所說，如果不取最大的那個的話在判斷函式里就要考慮完不成的情況，如果取最大就不用考慮如果不取最大值check函式那里可能要加一些判斷條件

整體代碼如下（不做過多解釋，理解就可）

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;

int n,m;
int a[N];
int l,r;

bool check(int x){
	int sum = 0,cnt = 0;
	for(int i = 0;i < n;i ++){
		if(sum + a[i] <= x) sum += a[i];
		else sum = a[i],cnt++;
	}
	return cnt < m;
}

int main(){
	scanf("%d %d",&n,&m);
	
	for(int i = 0;i < n;i ++){
		scanf("%d",&a[i]);
		r += a[i];
		if(a[i] > l) l = a[i];	
	}
	//r = 1000000000;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	} 
	printf("%d",l);
	return 0;
}

小數二分就不再過多提及，主要再check函式，可以多加摸索取找到解題思路（不是因為我不熟才不提及的）
總之呢，做二分題重點還在理解題意、找對模板、寫好check函式
（以上為個人理解，我還是個編程菜鳥，嘻嘻~）