二分答案思想的总结——在一个区间里面用二分的方法找满足check函数的模板

二分答案思想的总结——在一个区间里面用二分的方法找满足check函数的模板

典型问题：切蛋糕，切木棒，求满足条件（通常是大于等于给定的n),求长度的最大值。

数学小知识：长度为h，宽度为w的长方形，切长度为a的正方形，可以切ans=(h/a)*(w/a)个。 

二分的代码实现思想：利用左右边界l,r不断去卡范围一直到（l>r);

核心代码模板

while(l<=r) 
	{
		int m=l+(r-1)/2;
		if(check(m))
		{
			ans=m;
			l=m+1; 
		}
		else
		r=m-1; 
	}

 注意中间量int m=l+(r-l)/2;同时check函数也比较重要； 

典型例题：蓝桥杯，分巧克力 

#include
using namespace std;
const int N=1e5+10;
int n,k,h[N],w[N];
bool check(int m)
{
	long long c=0;
	for(int i=0;i=k)
	  return 1;
	  return 0;
} 
 
int main()
{
	cin>>n>>k;
	for(int i=0;i>h[i]>>w[i];
	int ans=1;
	int l=1,r=100000;//范围卡到最大的总的长度哪里;
	while(l<=r) 比如最后到了6,7这里;m取的是6且满足条件,l=7进入下面一个循环，加入l=m=7满足条件则要取7了 
	{
		int m=l+(r-1)/2;
		if(check(m))
		{
			ans=m;
			l=m+1;//调大； 同时也是迎合while条件舍掉 ； 
		}
		else
		r=m-1; 
	}
	printf("%d",ans);
	return 0;
}

模板的要点：l初始的时候设置为大边界1,1e5;

                     m=l+(r-l)/2;

                     while(l<=r)等于的也要写进去不写的话最后相等的值m的判断缺失导致问题