二分查找与二分答案题解

此类题目的特征为数据量大，数据为升序或降序

根本目的是 通过二分法快速缩小答案范围，然后对比数据或验证答案

2.1二分查找

输出时注意mid是否为第一个出现的答案

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1000000];
 4 int main(void)
 5 {
 6     int n,m,l,r,mid,serch;
 7     //输入 
 8     cin>>n>>m;
 9     for(int i=0;i<n;i++)
10     {
11         cin>>a[i];
12     }
13     //左l，右r 二分查找
14     for(int i=0;i<m;i++)
15     {
16         l=0,r=n-1;
17         cin>>serch;
18         while(l<=r)
19         {
20             mid=(l+r)/2;
21             if(a[mid]==serch)
22             {
23                 if(a[mid-1]==a[mid]&&mid!=0)
24                 {
25                     r=mid-1;
26                     continue;
27                 }
28                 cout<<mid+1<<" ";
29                 break;
30             }
31             else if(a[mid]>serch)r=mid-1;
32             else l=mid+1;
33         }
34         if(l>r)cout<<"-1 ";
35     }
36     return 0;
37 }

2.2二分答案

mid存储被测试的答案，用all存储该答案能存下的牛总数

#include<bits/stdc++.h>
using namespace std;
int a[100000];
int main(void)
{
    int n,c,l=1,r,mid,all;
    cin>>n>>c;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    r=a[n-1]/c;
    while(l<=r)
    {
        all=1;
        mid=(l+r)/2;
        for(int i=1,j=0;i<n;i++)
        {
            if(a[i]-a[j]>mid)
            {
                all++;
                j=i;
            }
        }
        if(all>=c)l=mid+1;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}

2.3二分答案

同样用mid存储被测试的答案，用b存储目前所在位置，用all存储移走的石头数

#include<bits/stdc++.h>
using namespace std;
int a[50001]={0};
int main(){
    int l,n,m,mid,left=1,right,all,b;
    cin>>l>>n>>m;
    right=l;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1]=l;
    while(left<right-1)
    {
        mid=(right+left)/2;
        b=0;
        all=0;
        for(int i=1;i<=n+1;i++)
        {
            if(a[i]-b>=mid)b=a[i];
            else all++;
        }
        if(all>m)right=mid;
        else left=mid;
    }
    if(n==0)cout<<l;
    else cout<<left;
    return 0;
}