听课总结

特征词 : 单调有序数组,求最大值最小/最小值最大

#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) scanf("%d",&q[i]);
    while (m--)
    {
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while (l<r)
        {
            int mid=l+r>>1;
            if (q[mid]>=x) r=mid;
            else l=mid+1;
        }
        if (q[l]!=x) cout<<"-1 -1"<<endl;
        else
        { 
            cout<<l<<" ";
            int l=0,r=n-1;
            while (l<r)
            {
                int mid=l+r+1>>1;
                //这里不+1会死循环,如只有2 2时,l=2,r=2,mid=2,l=mid就会死循环
                if (q[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

刷题总结

做题步骤 : 
1.怎么分 
答案是啥就分啥
2.套模板
是111000型,还是000111型,套对应的模板

二分问题有两种
1.000111型 : 套第一个模板
>找满足某个条件的第一个数
>找最小值(满足该边界的左边界)
2.111000型 : 套第二个模板
>找满足某个条件的最后一个数
>找最大值(满足该边界的右边界)

小数二分
一般为while(l+1e-8<r)[如果超时了,可能是取不到1e-8]
l=mid,r=mid