# 二分答案

二分答案算法很困扰的地方其实就是写好 边界条件
又要写好 check 判断函数的边界，又要写好循环二分的边界条件

# 二分答案的适用情况

有确切的答案区间，最终答案一定在这个区间中
题目中往往需要：求... 最小值的最大值或者求... 最大值的最小值

所以我们就可以通过二分这个答案区间去不断缩小答案区间
最终找到答案。

但最终的答案区间可能有很多数值都符合题目条件
需要去判断取这个数值区间的最小值还是最大值

二分答案便是为了解决这样的问题

# 二分答案的模版（整数）

模版分两种，一种是 尽量往左搜索答案（在从小到大的区间中便是搜最小值）
一种是 尽量往右搜（在从小到大的区间便是搜最大值）

在实际题目中需要判断往区间的哪个方向去搜

# check 判断函数

	int check（int mid）
	{
	// 按照题目条件判断
	if( )return 1;
	else return 0;
	}

# 往左

	int l,r,mid;
	while(l<r)
	{
	mid=(l+r)>>1;// 中点
	if(check(mid))r=mid;
	else l=mid+1;// 中点处再右移一个数
	}
	cout<<l;// 往左搜时，答案便是 l

# 往右

	int l,r,mid;
	while(l<r)
	{
	mid=(l+r+1)>>1;//+1 是在中点处再右移一个数
	if(check(mid))l=mid;
	else r=mid-1;// 在 mid 处 - 1 就又回到真正的中点
	}
	cout<<r;// 往右答案便是 r

# 思考

在记的时候要着重理解 $l$ 和 $r$ 的取值
思考两个模版的在不断二分时，为什么不会使断点处漏掉任何一个数

而且在 l 和 r 比较大的时候，要记得开 $long long$
或者把 $mid=（l+r)>>1$ 改成 $mid=l+（r-l）>>1$

想练练手了？

# 木材加工（洛谷 p2440）

# 题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $1cm$ ，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$ ，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$ 。

# 输入格式

第一行是两个正整数 $n,k$ ，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$ ，表示一根原木的长度。

# 输出格式

仅一行，即 $l$ 的最大值。

如果连 1cm 长的小段都切不出来，输出 0 。

# 样例 #1

# 样例输入 #1

	3 7
	232
	124
	456

# 样例输出 #1

# 提示

# 数据规模与约定

对于 100% 的数据，
有 $1\le n\le 10^5$ , $1\le k\le 10^8$ , $1\le L_i\le 10^8(i\in[1,n])$

二分答案的做题思路往往要转变一下，在这题中

答案一定在区间 0 ~ 所有木头长度之和 sum 中

所以我们不是去思考这些木头锯成 k 段最大能锯多长
而是去思考锯成 l 这么长，能锯多少段

二分答案往往要以这个思路来思考
所以我们二分的就是锯出来的小段的长度 l

	#include<iostream>
	using namespace std;
	long long n, k,a[100010],sum,m=0,l,r,mid,ans=0;
	long long check(int x)
	{
	ans = 0;
	for (int i = 1; i <= n; i++)
	{
	ans += (a[i] / x);
	}
	return ans;
	}
	int main()
	{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
	cin >> a[i]; m = max(m, a[i]); sum += a[i];
	}
	if (sum < k) {cout << "0" << "\n"; return 0;}// 特判
	l = 1, r = m;
	while (l < r)// 往右搜，搜最大值
	{
	mid = (l + r + 1) >> 1;
	if (check(mid) >= k)l = mid;
	// 要着重判断二分取等的时候，怎么继续缩小区间
	else r = mid - 1;
	}
	cout << r << "\n";
	return 0;
	}

其他练习可以参考

洛谷砍树 P1873
洛谷跳石头 P2678
洛谷数列分段 P1182
洛谷路标设置 P3853

# 实数二分（浮点数二分）

以上只是在整数区间进行二分
但是当然有实数二分了

不过实数二分比较简单，只有一个模版
循环条件是判断到没到某个精度（比如 1e-5）

	int l,r,mid;
	while(r-l>1e-5)
	{
	mid=(l+r)/2;
	if(check(mid))l=mid;
	else r=mid;
	}

练习题：
Problem - 371C - Codeforces

基础算法