智商恢复训练(二分，三分)

╰半夏微凉° 2021-09-17 23:42 323阅读 0赞

整数二分  
**1**.mid在左边， \[ l , m i d \] 与 \[ m i d + 1 , r \] \[l,mid\] 与\[mid+1,r\] \[l,mid\]与\[mid\+1,r\]（在左边的意思是当mid符合条件时，寻找的范围变成左半边）

int bsearch(int l, int r)
    { 
        while(l < r)
        { 
        	int mid = l + r >> 1;
        	if(check(mid)) r = mid;
        	else l = mid + 1;
        }
        return l;
    }

**2**.mid在右边， \[ l , m i d − 1 \] 与 \[ m i d , r \] \[l,mid-1\] 与\[mid,r\] \[l,mid−1\]与\[mid,r\]

int bsearch(int l, int r)
    { 
        while(l < r)
        { 
        	int mid = l + r + 1 >> 1;
        	if(check(mid)) l = mid;
        	else r = mid - 1;
        }
        return l;
    }

**3**.关于溢出问题

int mid = l + 0LL + r >> 1;

实数二分  
**1**.eps一般为要求精度的1/100，若觉得不靠谱，可设置二分次数

double l = a,r = b;
    while(r - l > eps)
    { 
    	double mid = (l + r) / 2;
    	if(check(mid)) r = mid;
    	else l = mid;
    }

三分

**1**.二分就是求边界，三分就是求最小值（最大值）

**poj2018Best Cow Fences**  
题意：给一个正整数的序列，求一个长度大于等于L，平均数最大的子段。

二分答案，用前缀和与双指针解决判定问题

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    
    const int maxn = 1e5 + 100;
    
    int n,m;
    int a[maxn];
    double f[maxn];
    bool check(double s)
    { 
    	rep(i,1,n+1)
    		f[i] = f[i-1] + a[i] - s;
    
    	double mi = 0;
    	int j = 0;
    	rep(i,m,n+1)
    	{ 
    		mi = min(mi,f[j]);
    		j++;
    		if(f[i] >= mi)
    			return true;
    	}	
    	return false;
    }
    
    int main(int argc, char const *argv[])
    { 
    	scanf("%d%d",&n,&m);
    	double l = 0,r = 0;
    	rep(i,1,n+1)
    	{ 
    		scanf("%d",&a[i]);
    		r = max(r,(double)a[i]);
    	}
    	while(r - l > 1e-5)
    	{ 
    		double mid = (r + l) / 2;
    		if(check(mid)) l = mid;
    		else r = mid;
    	}
    	printf("%d\n",(int)(r * 1000));
    	return 0;
    }