二分法

简介：

网上模板很多，看得眼花缭乱，搞得不知道用哪种好，我自己就用这种吧，这是前几天看那道冶炼金属那题看到得模板，这个模板应该也适用于很多题了(闭区间)

• 寻找靠左的数

while(l<=r)
{
    int mid=l+((r-l)>>1);
    if(a[mid]>=x)r=mid-1;
    else l=mid+1;
}
if(a[l]==x)return l;
else return -1;

由上面的图示可以看成，如果是寻找左边的数最终的while(l<=r)最终结束的条件是r在左侧，而l在右侧，因此q[l]==x,那么我们就找到了我们想要且靠左的数的位置

• 寻找靠右的数

while(l<=r)
{   
    int mid=l+((r-l)>>1);
    if(a[mid]<=x)l=mid+1;
    else r=mid-1;
}
if(a[r]==x)return r;
else return -1;

由这个图示可知，如果要寻找右边的数，最终while(l<=r)的结束条件是r在左侧，l在右侧，那么q[r]==x的话，r就是我们找的靠右侧的数的位置

例题:

【洛谷】P1102 A-B 数对

A-B 数对

题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A-B=C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A-B=C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据，$1\le N\le 2000$。

对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$0\le a_i<2^{30}$，$1\le C<2^{30}$。

2017/4/29 新添数据两组

思路：

这题先走了个弯路，即排序后，先打算固定一个数，然后看后面的数减去前面的数，如果等于c，则记一次数，然而这种方法就是常说的暴力法，数据量大的时候会超时，我们的计算机1s内能算1e7次到1e8次，超过这个数必然超时了

因此正解是利用二分，先移项，A=B+C,C是固定的，那么我们去遍历数组，数组的每一项都在每一次循环作为B,然后加上C的得到数A,然后在去数组中寻找A的位置，找到1个加入答案，没找到就不加，注意二分一定要先排序排序排序，还有就是我们在数据范围很大的时候一定要开long long ，如果判断不准，那就开着long long

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL sum=0;
LL bserach1(LL q[],LL n,LL a)
{
   LL l=0,r=n-1;
   LL mid=l+r>>1;
   
   while(l<=r)
   {
       mid=l+r>>1;
       if(q[mid]>=a){r=mid-1;}
       else l=mid+1;
   }
   if(q[l]==a)return l;
   else return -1;
}
LL bserach2(LL q[],LL n,LL a)
{
   LL l=0,r=n-1;
   LL mid=l+r>>1;

   while(l<=r)
   {
       mid=l+r>>1;
       if(q[mid]<=a){l=mid+1;}
       else r=mid-1;
   }
   if(q[r]==a)return r;
   else return -1;
}
int main()
{
    LL n=0,c=0;LL q[1000000]={0};
    cin>>n>>c;
    for(LL i=0;i<n;i++)cin>>q[i];
    sort(q,q+n);
    LL res1=0,res2=0;
    for(LL i=0;i<n;i++)
    {   
        LL a=q[i]+c;
        res1=bserach1(q,n,a);
        if(res1==-1)continue;
        else
        {
         res2=bserach2(q,n,a);
        }
        sum+=(res2-res1+1);
    }
    cout<<sum;
    return 0;
}

交完后发现#4 RE了，一直不知道为什么，后来问了学长才知道是初始化的原因。

RE的错误点一般是在和溢出有关，数组溢出，还有就是未初始化，未初始化这个数可能会很大，导致溢出

所以注意一定要初始化！！！初始化！！！初始化！！！

[蓝桥杯 2023 省 B] 冶炼金属

[蓝桥杯 2023 省 B] 冶炼金属

题目描述

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 $V$，$V$ 是一个正整数，这意味着消耗 $V$ 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 $V$ 时，无法继续冶炼。

现在给出了 $N$ 条冶炼记录，每条记录中包含两个整数 $A$ 和 $B$，这表示本次投入了 $A$ 个普通金属 O，最终冶炼出了 $B$ 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 $N$ 条冶炼记录，请你推测出转换率 $V$ 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 $N$，表示冶炼记录的数目。

接下来输入 $N$ 行，每行两个整数 $A,B$，含义如题目所述。

输出格式

输出两个整数，分别表示 $V$ 可能的最小值和最大值，中间用空格分开。

样例 #1

样例输入 #1

3
75 3
53 2
59 2

样例输出 #1

20 25

提示

【样例说明】

当 $V=20$ 时，有：$\lfloor \frac{75}{20}\rfloor =3,\lfloor \frac{53}{20}\rfloor =2,\lfloor \frac{59}{20}\rfloor =2$，可以看到符合所有冶炼记录。

当 $V=25$ 时，有：$\lfloor \frac{75}{25}\rfloor =3,\lfloor \frac{53}{25}\rfloor =2,\lfloor \frac{59}{25}\rfloor =2$，可以看到符合所有冶炼记录。

且再也找不到比 $20$ 更小或者比 $25$ 更大的符合条件的 $V$ 值了。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1\le N\le 10^2$。

对于 $60\%$ 的评测用例，$1\le N\le 10^3$。

对于 $100\%$ 的评测用例，$1\le N\le 10^4$，$1\le B\le A\le 10^9$。

蓝桥杯 2023 省赛 B 组 C 题。

==思路:==这题用二分是可行的,用两次二分，一次寻找靠左边的数，即我们的vmin，另一次则寻找靠右边的数，即我们的vmax

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n;
int a[N], b[N];
bool check1(int v)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] / v > b[i])return false;
    }
    return true;
}
bool check2(int v)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] / v < b[i])return false;
    }
    return true;
}
int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i] >> b[i];
    int l = 0, r = 1e9, vmin = 0, vmax = 0;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (check1(mid)) { vmin = mid; r = mid - 1; }
        else l = mid + 1;
    }
    l = 1, r = 1e9;
    while (l <= r)
    {
        int mid = l + ((r - l) >> 1);
        if (check2(mid)) { vmax = mid; l = mid + 1; }
        else r = mid - 1;
    }
    cout << vmin<< " " << vmax;
    return 0;
}