总结二分法

杨辉三角形（快速查找唯一值,mid型)

//二分法解//流程：最大列->起点行->2k--n之间究竟哪一行（二分+排列组合）->找到行数就等差数列+对应位置#include<stdio.h>
#include<stdlib.h>//注意排列组合的规律是建立在第0行和第0列的基础！
long C(long a,long b,long n)//C排列组合算法
{long res=1;//一开始要赋值为1！for(long i=a,j=1;j<=b;i--,j++)//一个循环就可以实现C排列组合{res=res*i/j;if(res>n){return res;}//放循环里判断！优化算法//一旦这个res在循环中的结果已经有了超过n的就马上退出，不要再//等它全部遍历完返回再判断！}return res;}int main(int argc, char *argv[]){long n,k;scanf("%ld",&n);    // for(k=0;;k++)errfor(k=16;k>=0;k--)//为什么正着输出不行//因为我们是计算第一次出现的数字//那就必须要在最后面的列开始找//一直往前面的列逐个寻找//你从正着遍历就是直接输出最近的也就是第1列//第一列必会出现这个数的答案，因此直接输出了//就不是第一次出现//所以不可以不计算//k代表需要遍历列数//这是根据最大测评数据推出的,1e9//计算器难计算的，就可以借助编程来计算//自己写一个排列组合的函数，该题也用到了这个函数//代数看看最大只可能出现在哪即可//求出最大列数不可能在17列，C17/34大于1e9//因此可以得知在[0,16]之间//k--能写成k++，肌肉记忆是吧?{long l=2*k,r=n;//l等于2k是对应行数//因为一开始从最大列开始算//也就只有2k以后的行才会有这么多的有效列//所以从这以后开始查找//l是需要遍历的行数,//这里等于2k仅仅只是满足最大情况//当最大情况不为所求时就用二分法//矫正行数，这就是为什么二分法只分行数//列不变，也是定一动一.//int mid=(l+r)/2;//这个要放里面，因为每次二分都是不同位置的！while(l<=r) //二分法//二分法可以是mid值作为想要输出的结果//也可以使用right和left作为想要的输出结果//具体不同题设判断如何用l,r还是mid//当结果不用l、r时，我们就不需要考虑//l与r究竟谁赋值mid了。直接舍弃即可(求Mid)//因为我们要求的只有唯一值就是行数//所以可以直接使用mid//直接用mid就是固定的//  r=mid-1;//  l=mid+1;//类似的模板//(因为既然mid值都不为所求,自然都舍弃)//l是左边界，r是右边界(我们求行数所以左边界为l)//意思就是从l的范围开始找//而r是上限，//所寻找的行永远小于等于n行，所以可以设边界//最差的情况就是数字等于行数//即所找的数字在第n行第二位的情况//所以r=n{long mid=(l+r)/2;//划分中点//我们的二分法是为了寻找所求数字的//所在的行和列，而不是直接找到该数字！if(C(mid,k,n)==n)//mid是所寻找的行不是数字//中点恰好是要找的行//放在全局变量就不用上传这么多参数了{printf("%ld",(1+mid)*mid/2+k+1);//这里是等差数列，每一行的全部是//d=1的等差，1+2+3+......//注意我们求的是数字数量之和不是大小之和//所以(a1+an)*n/2//这里的等差数列是把原来的第0列看成第一列了//这里的等差数列就没有第0列//因此求出来的mid行数就是上一行//恰好可以排等差数列,剩下的加上k+1即可//k+1是因为排列组合有第0列，既然是在使用这个//规律的基础上，就必须遵循第0列开始，//而第0列->k列就是k+1//注意过程的选取，是等差数列的过程// 还是处在排列组合的过程return 0;}else if(C(mid,k,n)>n)r=mid-1;//mid太大就只可能在左边一堆，//然后循环再分一次else//mid太小l=mid+1;}}return 0;
}

递增三元组(求极限/多种情况最优最佳结果，l、r型）

#include<bits/stdc++.h>//递增三元组using namespace std;
int main()
{int a[100000],b[100000],c[100000];int n;long long ans=0;cin>>n;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];for(int i=0;i<n;i++)cin>>c[i];sort(a,a+n);//直接写出首尾就ok了sort(c,c+n);int left,right;
for(int i=0;i<n;i++)//枚举b
{//找出比b小的最大的a,比b大的最小的cleft=0,right=n-1;while(left<right){int mid=(left+right+1)/2;if(b[i]<=a[mid])//当前a的值大于等于b，我也不要了//a太大，我就缩小//注意，这个小于等于要放在一起因为都归为mid不可取的一边//如果只写<，那么等于在下面就无法把等于这种情况去除.right=mid-1;elseleft=mid;//当前mid满足条件可取}int x=right;left=0,right=n-1;
while(left<right)
{int mid=(left+right)/2;if(b[i]>=c[mid])//条件不满足题意，mid值不要left=mid+1;elseright=mid;//符合,mid可取}
int y=right;if(a[x]<b[i]&&b[i]<c[y])
{// ans+=(x+1)*(n-y);errans+=(long long)(x+1)*(n-y);//两个相乘是因为排列组合//定下1个b，每一种的a都有n-y个c的情况.//一个数据错了，这里相乘计算大数据会溢出//所以要扩大数据类型！//但是给x,y修改类型竟然也能过，我不知道为什么//但逻辑来讲还是改这里的数据类型比较严谨
}}cout<<ans;return 0;
}

总结：

如果二分法输出的是l、r，那么循环搜索的原理就是当l==r时结束搜索

此时l与r的值都是一样的，都能作为结果输出

循环条件为l<r

等于时就停止循环了，不要写l<=r不然会死循环

而mid作为结果输出时

我不关心l、r的结果

我要求的是mid,而l==r时，同样仍然还可以再求中间值

如果是这种情况也就是mid==l==r

那么也要将这个结果赋值给mid，要不然你的mid也是错的

因此求mid时条件为l<=r

求mid的二分的前提是找一个值,是相当于只是优化算法

加快了遍历速度，就是每次都遍历一半，其实完全可以用for循环暴力遍历

当前是唯一值，线性的范围内，只要这个mid符合条件我就马上退出循环了

不满足就继续分

这个是查找唯一的下标值

而求l、r是不同的，这个二分相当于是求一个边界和极限

因为l、r可以不断移动，所以是通过调整l、r的位置来确定唯一的值

当l==r时，就是那个划分边界的点，此时的mid只是作为调位的一个工具

初始的时候l、r距离很大，后来不断二分缩小他们的位置，最后相等时

即确定了极限和边界位置.

求l、r的时候才真正体现了二分的优越性.

mid更像是快速查找唯一值，而l、r则似求一个满足当前条件的一个极限值

明显的特征就是l、r的情况有多个结果，只是在多个结果中挑选出一个

最佳最优的情况，也就是极限，就要用l、r来收缩求最佳结果.