分治算法详解：二分与三分专题-CSDN博客

本文链接：https://blog.csdn.net/weixin_45388515/article/details/104084103

本文详细介绍了二分与三分算法的应用。通过分析不同问题，如最大最小距离、二次函数优化和热膨胀问题，展示了如何利用二分和三分解决具有单调性和凹凸性的问题。此外，还讨论了在实际编程中需要注意的精度和循环条件等细节。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题面

I - 二分 HYSBZ - 1734
农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,…,xN (0 <= xi <= 1,000,000,000). 但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

第一行：空格分隔的两个整数N和C

第二行—第N+1行：i+1行指出了xi的位置

第一行：一个整数，最大的最小值

Sample Input
5 3
1
2
8
4
9

Sample Output
3

（把牛放在1，4，8这样最小距离是3 ）

分析

要使最小值最大，答案具有单调性，可以二分答案转化为判定
在这里用的二分是闭区间 [ l,r ]
特别注意一点，这里要用 mid=(l+r+1)>>1 而不能 mid=(l+r)>>1
当 l r 相差1时，即 l+1=r 时，mid=(l+r)>>1 向下取整 = l
执行分支 l=mid =l 会导致死循环，因为区间[ l,r ] 没有缩小，一直停留在 l+1==r
执行分支 r=mid-1 =l-1 会以 l>r 结束, 而不是 l=r
而用 mid=(l+r+1)>>1 则可以避免 mid 向下取整时取到左端点 l

代码


#include<iostream>
using namespace std;
#include<stdio.h>
#include<algorithm> 

int N,C;
const int MAX_N=1e5+5;
int a[MAX_N];

bool check(int d)
{
   
	int pre=a[0],cnt=1;			//第一个必放 
	for(int i=1;i<N;i++){
   
		if(a[i]>=pre+d) {
    
			pre=a[i]; cnt++;
			if(cnt>=C) return 1;
		}
	}
	return 0;
}

int bisearch(int l,int r)
{
   
	while(l<r){
   
		int mid=(l+r+1)>>1;			 特别注意 向下取整 避免取到 l  
		if(check(mid)) l=mid;
		else r=mid-1;			//
	}
	//printf("l=%d r=%d\n",l,r);			//l==r时结束 
	return l;