【思想】二分

更新于 分类于 ， 阅读次数： 本文字数： 887 阅读时长 ≈ 1 分钟

二分是解决有单调性问题的一种方法。

二分答案

  • 条件：单调闭区间
  • 题面：最大值的最小值，最小值的最大值。
  • 套路：二分+判断函数，二分提供一个mid值，判断函数根据mid值操作并返回是否符合题目条件，从而得到该mid值是否成立，判断二分往哪个区间取。（注：二分的是答案区间）
  • 技巧1：注意特定值符合条件时（即条件不是不等式），判断函数返回计算值，在二分中判断该值符合条件/大于/小于条件分别如何处理
  • 技巧2：对于一组数据里有多组数据需要进行相同处理，最终需要得到某组数据的位置，可以二分这些数据，减少处理时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool check(T x)
{
    T ans=0;
    for(int i=0;i<n;i++)
        //处理操作；//注意该操作中千万不能改变原数组的值，否则后面的二分就失败了
    return ans>=m;
}
//整数二分
void solve()//求最小值的最大值
{
    ll lb=0,rb=INF;
    while(rb-lb>1){
        ll mid=(lb+rb)/2;
        if(check(mid)) lb=mid;
        else rb=mid;
    }
    printf("%lld",lb);
}
//实数二分
void solve()
{
    double lb=0,rb=INF;
    while(rb-lb>eps) { 
        ll mid=(lb+rb)/2.0;
        if(check(mid)) lb=mid;
        else rb=mid;
    }
    printf("%lld",lb);
}

三分

1
2
3
4
5
6
7
8
9
10
void solve()
{
	while(r-l>eps)
	{
		double lmid=l+(r-l)/3,rmid=r-(r-l)/3;
		if(f(lmid)<=f(rmid)) l=lmid;
		else r=rmid;
	}
	printf("%.5lf",r);
}