你绝对不知道的二分新使用

2020.3.8
刚刚复盘前两天做的LeetCode475，一个关于二分的题。又发现一点。
当我们在找一个num中存在的数字的时候，模板是没有问题的。但是需要一个num中离key最近的一个数字时，可能会出现问题。

当key在最大与最小值之间时，left和right刚刚好一个右一个左连续的。
但是当key小于最小值时，最后一次循环right-1，会让left：0，right：-1；
同理当key大于最大值时，最后一次循环left+1，会让left：size-1，right：size；

只需要打一个补丁就好了

        if(left==heatersSize) low--;
        if(right==-1) high++;
        dis=my_min(my_abs(houses[h]-heaters[low]),my_abs(houses[h]-heaters[high]));

---

2020.3.6
今天群里分享了二分，恰好看到一个公众号对二分的理解，感觉这一波应该是圆满了。

首先我们先明白二分的大致模板：

left=0,right=num.length()-1;
while(left<=right){
    mid=left+(right-left)/2;
    if(num[mid]==key){}
    else if(num[mid]<key) {
        left=mid+1;
    }else if(num[mid]>key){
        right=mid-1;
    }
}

今天要解决的问题就是 +-1 和 取不取等号 的问题。
为了解决这个问题，我们重新审视一下我们的模板代码。

left=0,right=num.length()-1;

我们的区间现在是整个数组的闭区间，即一左一右两个指针必须在分区间后同样严格指向该区间两端。
···
while(left<=right)
···
当到达left==right 的时候，继续循环。
此时mid=left=right，本次循环就检测这一个数，该数本身闭区间，即[2]。

left=mid+1; / right=mid-1;

原本我们的区间是{[left, mid, right]}
mid已经检测过了，同时要严格保证闭区间，就应该相应改动区间为{[left， X]， mid，right}或者{left，mid[X，right]}

所以只需要牢记区间统一即可。在这里我在po一个其他样式的代码。

left=0,right=num.length();
while(left<right){
    mid=left+(right-left)/2;
    if(num[mid]==key) {}
    else if(num[mid]<key) left=mid+1;
    else if(num[mid]>key) right=mid;  
}
if(left>=num.length()) Do
else if(num[left]==key) Do

当然，如果while里面非要写 = ，那么会漏掉一个left的比较，循环结束后要判断left越界或者是等于key，注意一下，left一直在往right跑，所以if的语句，对应right判断应该是小于0。最好不要用这种打补丁方式，po一下LeetCode中532题对比

        int low=i+1,high=numsSize-1;
        while(low<high){
            int mid=(low+high)/2;
            if(nums[mid]==(nums[i]+k)){cnt++; break;}
            else if(nums[mid]<(nums[i]+k)) low=mid+1;
            else if(nums[mid]>(nums[i]+k)) high=mid-1;
        }
        if(low<numsSize && low==high && nums[low]==(nums[i]+k)) cnt++;
    }

和

        int low=i+1,high=numsSize-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]==(nums[i]+k)){cnt++; break;}
            else if(nums[mid]<(nums[i]+k)) low=mid+1;
            else if(nums[mid]>(nums[i]+k)) high=mid-1;
        }

就离谱！

---

今天实验室讲了二分，然鹅！！我没起来！！！
于是，只有自己看一看，学一学二分思想。

首先，二分是有适用条件的，一般来说，答案必须是离散的点，并且我们二分的是答案。同时，二分必须要满足单调性，即假设t0是答案，那么大于/小于t0的都可以满足条件，小于/大于t0的都不满足条件。

Matrix（POJ3685）
题意：给你一个NXN的矩阵，告诉你矩阵中(i,j)点的值为 i^2 + 100000 × i + j^2 - 100000 × j + i × j，问第M小的数字是多少。

分析：其实刚刚拿到题目的时候，就想到了之前做的4 Values whose Sum is 0(POJ2785)这道题。不过两道题还是有不一样的，就本题而言，由给你的公式我们可以看出来，当我们固定j不动时，i是单调递增的，即满足单调性，我们就可以二分答案了。
但是这样还不够，这只是相当于枚举了j的值，我们还需要枚举i的值才能得到答案。怎么枚举能，肯定就是看小于 枚举答案的 数字的个数。我们可以根据每一列的单调性就可以二分了。
这就是传说中的二分套二分！！！

#include<bits/stdc++.h>

#define ll long long

using namespace std;
ll n,m;
ll isOk(ll i,ll j){
    return i*i+100000*i+j*j-100000*j+i*j;
}

bool check(ll x){
    ll res=0;
    for(ll j=1;j<=n;j++){
        ll l=1;
        ll r=n;
        ll tmp=0;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(isOk(mid,j)<=x){
                tmp=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        res+=tmp;
        if(res>=m) return true;
    }
    return false;
}

void Solve()
{
    scanf("%lld%lld",&n,&m);
    ll l=-(ll)100000*n;
    ll r=n*n+(ll)100000*n+n*n+n*n;
    ll ans;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    printf("%lld\n",ans);
}

int main()
{
    //FILEIN
    //FILEOUT
    //std::ios::sync_with_stdio(false);
    int Case=1,cases;
    scanf("%d", &Case); cases=Case;
    while(Case--){
        //printf("Case #%d:",cases-Case);
        Solve();
    }
    return 0;
}

还有一道二分卡精度的问题Cable master(POJ1064)

题意：给你n个长度不等的线段，让你切割这些线段，使得最后有m段一样长的线段，问这m长的线段的长度是多少。

分析：其实二分还是很好想的，还是用单调的特点，假设这m段的长度为ans，当长度大于ans时，就不能达到m段；当长度小于ans时，就可以择一定能切割刀大于等于m段。
主要这道题有精度问题，题目中答案在1 meter到1 kilometer之间，输出的时候要精确到centimeter。同时还要注意一点，如果你的数值是3.457，那么

/********************************
Author: Audrey_H
Motto:talk is cheap,show me the code.
********************************/

//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define lowbit(x) (x&(-x))
#define PB(x) push_back(x)
#define ll long long
#define PI acos(-1.0)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug printf("!!");

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;

const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 1e5+100;
const int maxe = 1e6+100;

using namespace std;

double num2[maxn];
int n,k;

bool check(double x){
    int tnum=0;
    for(int i=1;i<=n;i++){
        tnum+=(int)(num2[i]/x);
    }
    if(tnum>=k) return true;
    else return false;
}

void Solve()
{
    scanf("%d%d",&n,&k);
    double sum=0;
    for(int i=1;i<=n;i++){
        scanf("%lf",&num2[i]);
        sum+=num2[i];
    }
    double l=0,r=sum;
    double ans=0;
    for(int i=1;i<=100;i++){
        double mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            l=mid;
        }else{
            r=mid;
        }
    }
    if((int)(ans*1000)%10>=5){
        ans-=0.005;
    }
    printf("%.2f\n",ans);
}

int main()
{
    //FILEIN
    //FILEOUT
    //std::ios::sync_with_stdio(false);
    int Case=1,cases;
    //scanf("%d", &Case); cases=Case;
    while(Case--){
        //printf("Case #%d:",cases-Case);
        Solve();
    }
    return 0;
}