0.前言

通过几道题目 切割钢管、木材加工、切割绳子、均分蛋糕 四道题，尝试了二分法中最大化平均值问题。

然后，下面进行简单的对比和总结。

1.简单总结

while(l < r){          int mid = (l + r) >> 1;// 二分查找  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          }          if(cnt >= k){               //那么这个mid是可行的，我们就可以扩大左边界值              l = mid + 1;          }else{              r = mid;              //否则的话，这个mid就是太高了，就可以把右边界缩小          }      }

写法2：

while(l <r-1){          int mid = (l + r) >> 1;// 二分查找  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          }          if(cnt >= k){               //那么这个mid是可行的，我们就可以扩大左边界值              l = mid;          }else{              r = mid;              //否则的话，这个mid就是太高了，就可以把右边界缩小          }      }

写法2进行简单变换还可以写成：

while(l+1 <r){          int mid = (l + r) >> 1;// 二分查找  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          }          if(cnt >= k){               //那么这个mid是可行的，我们就可以扩大左边界值              l = mid;          }else{              r = mid;              //否则的话，这个mid就是太高了，就可以把右边界缩小          }      }

如果出现小数，那么可以这么写：

while ((right-left)>1e-4)   {  	mid=(left+right)/2;  	for (i = 0; i < n; i++)  		num += (int)(a[i] / x);  	if(sum>=k)  		left=mid;  	else  		right=mid;  }  //1e-4=0.0001  //等价于下面这样:   while (left+1e-4<right)   {  	mid=(left+right)/2;  	for (i = 0; i < n; i++)  		num += (int)(a[i] / x);  	if(sum>=k)  		left=mid;  	else  		right=mid;  }

注意: 这类题目的最大值一般通过循环求出，一般单体的最大值作为初始右端点，或者单体和的最大值作为右端点。

然后，有一类写法带等号

变形：（带等号的左右端点都要变）

while(l <= r){          int mid = (l + r) >> 1;// 二分查找  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          }          if(cnt >= k){               //那么这个mid是可行的，我们就可以扩大左边界值              l = mid + 1;          }else{              r = mid - 1;              //否则的话，这个mid就是太高了，就可以把右边界缩小          }      }

2.题目扩展

可以有单一的线条类型，变成复杂的面积、体积等类型。比如均分蛋糕

3.说明

上述过程，我们大部分都是在取左端点，其实可以取右端点。比如下面这两个代码模板：

取左端点：

while (l < r) {  	int mid = (l + r) / 2;  	if (judge(mid))  		r = mid;//judge()函数判断是否在范围内，为布尔型  	else  		l  = mid + 1;//避免死循环  }  return l;

取右端点：

while (l < r) {  	int mid = (l + r + 1) / 2;//+1避免死循环  	if (judge(mid))    		l = mid;  	else    		r = mid - 1;  }  return 1;

4.本质

二分：自定义某一性质，让区间的左边元素均不满足，右边元素均满足。或者反过来。

(adsbygoogle = window.adsbygoogle || []).push({});