二分法求解最大最小值模板

Love The Way You Lie 2022-05-14 04:19 235阅读 0赞

二分法题解：[https://www.cnblogs.com/hyl2000/p/5734908.html][https_www.cnblogs.com_hyl2000_p_5734908.html]

这类问题有个明显的特征：使最小值最大或者使最大值最小。这个时候大概步骤就是先对读进来的数据进行排序（因为二分查找是在有序的数据上进行的）然后执行二分。其中二分里的check函数是最关键的部分，例如第一题中我们就是二分答案，然后在check中贪心的来安排牛的位置，看是否能够满足答案。而第二题也是二分答案，check中按我们求出的答案把不满足答案的石头撤掉，看是否能够满足答案。这就是check的大概思路：即检查是否能够满足答案。

二分中还有一个重要的细节：求最大值的最小值时mid=(l+r)/2，l=mid+1，r=mid；而查找最小值的最大值时mid=(l+r+1）/2，l=mid，r=mid-1。不然程序会陷入死循环，或者得不到正确答案。

最后一点就是实数二分的时候因为精度需要常常我们会让程序一直进行计算，然而由于计算时的精度误差，常常也会使程序效率低下或者死循环。一般来讲我们这时可以限制二分次数，一般60-70次即可满足精度需要，这样可以提高程序效率，避免TLE的情况出现。

最最后一点，这类问题数据量一般都非常大，记得用scanf读入，第一题我就因为用cin而TLE了，改成scanf之后马上就过了。。。。。

二分法求最大最小值模板：

#include<iostream>
    using namespace std;
    bool judge(int mid)//判断是否符合条件
    {
    	for(循环)
    	{
    		求解计数结果num，++num; 
    	} 
    	if(num与题目边界条件)
    		return true;
    	else
    		return false; 
    } 
    int main()
    {
    	int l, r, ans = 0;
    	l = ;//l和r的具体值要看题目是需要枚举的什么 
    	r = ;
    	while(l <= r)
    	{
    		int mid = (l+r)/2;//mid = l + (r-l)/2
    		if(judge(mid))
    		{
    			ans = mid;
    			l = mid + 1;//也有可能不是1，可能是一个小数，要看具体的间距 
    		}
    		else
    		 	r = mid -1;
    	 } 
    	 cout << ans << endl;
    	 return 0; 
    }

具体样例参考：

[https://blog.csdn.net/yanyanwenmeng/article/details/82292248][https_blog.csdn.net_yanyanwenmeng_article_details_82292248]

[https_www.cnblogs.com_hyl2000_p_5734908.html]: https://www.cnblogs.com/hyl2000/p/5734908.html
[https_blog.csdn.net_yanyanwenmeng_article_details_82292248]: https://blog.csdn.net/yanyanwenmeng/article/details/82292248