二分答案

二分法简介

为一高效查找方法，将搜索范围一分为二。
适用于有序数据集合，利用单调性减少不必要的枚举。

解题步骤

研究数据结构的单调性。

确定最大区间[L,R],确保分界点一定在里头，若以R为答案，区间为[L+1,R]（若为0到n，则L=-1，R=n），若以L为答案，答案区间为[L,R-1]（同理）。
可以参照二分查找lower_bound()与upper_bound()

确定check函数，一般传入mid，返回mid所属区域或返回一个值。

计算中点mid = (L+R)/2，用check判断该移动L或R指针。

二分答案

较为常见，需要发现某个单调的函数，然后对其二分。
常见模型：
二分框架 + check函数
一般对答案进行二分，然后在枚举出某个可能解后判断其是否可以更有或合法，从而不断逼近最优解。

模板

bool check(int mid){
	bool res = true;
	//do something to check the authority of mid...
	return res;
}

int main(){
	int l = 0, r = 1e9;
	while(l + 1 != r){
		int mid = (l + r) / 2;//先求中点
		//具体根据题意修改
		//或if(check(mid)<=m)之类的
		if(check(mid))l = mid;//根据check移动r或l
		else r = mid;
	}
	cout<< l << '\n';//具体输出啥根据题意判断
}

如最大的最近距离（最短距离最大是多少）。

例题

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2*1e5 + 10;
int L, n, m;
int num[N] = { 0 };

int check(int mid) {//假设最大的最小值为mid，求删除的石头数目
	int res = 0, lst = 0;//删除的石头数量
	for (int i = 1; i <= n; i++) {
		if (num[i] - num[lst] < mid) {//lst表示上一个石头
			res++;//比最小值还小，删除这个石头，也就是i++，此时删除石头数增加
			continue;
		}

		lst = i;
	}
	if (L - num[lst] < mid)return m + 1;//最后一块不能删，区间太靠后了，让R=mid

	return res;
}

//分析易得以区间右边界R为答案，以[L+1,R]为区间
void ans() {
	cin >> L >> n >> m;
	for (int i = 1; i <= n; i++)cin >> num[i];

	int l = 0, r = 1e9 + 5;

	//二分长度区间
	while (l + 1 != r) {
		int mid = (l + r) / 2;//mid表示当前查找的值，目的是找到最大的最小值，mid一直接近于目标值
		if (check(mid) <= m)l = mid;//最小距离mid，移走的石头数check(mid)
		else r = mid;//R的check一直大于m，直到L=m右区间，R=L-1，输出L即答案区间的右边界
	}

	cout << l << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;// cin >> T;
	T=1;
	while (T--) {
		ans();
	}
	return 0;
}