2025-01-19二分

二分查找

模板

bool check(int x){
    //判断函数
    return true
}

//[l,mid],[mid+1,r]
int bsearch_1(int l,int r){
    while (l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;   
}

//[l,mid-1],[mid,r]
int bsearch_2(int l,int r){
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

例题

数的范围

#include<bits/stdc++.h>
using namespace std;

int n,q,x;
const int N=1e5+5;
int a[N];

bool check_1(int mid){
    return a[mid]>=x;
}

bool check_2(int mid){
    return a[mid]<=x;
}

void work(){
    cin>>n>>q;
    for(int i=0;i<n;i++) cin>>a[i];
    while(q--){
        cin>>x;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(check_1(mid)) r=mid;
            else l=mid+1;
        }
        int sta=l;//第一个大于等于x的数

        l=0,r=n-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(check_2(mid)) l=mid;
            else r=mid-1;
        }
        int end=l;//第一个小于等于x的数

        if(a[sta]!=x||a[end]!=x) cout<<-1<<" "<<-1<<endl;
        else cout<<sta<<" "<<end<<endl;
    }
}

int main(){
    work();
    return 0;
}

P8647 蓝桥杯 2017 省 AB 分巧克力 - 洛谷 | 计算机科学教育新生态

#include<bits/stdc++.h>
using namespace std;

int n,k;
const int N=1e5+5;
int a[N],b[N];

bool check(int mid){
    int sum=0;
    //这里必须切整块的正方形，边角料不要，有点逆天
    for(int i=0;i<n;i++) sum+=(a[i]/mid)*(b[i]/mid);
    return sum>=k;
}

void work(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }

    //模板
    int l=1,r=N;
    while (l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;//[mid,r]
        else r=mid-1;
    }
    
    cout<<l<<endl;
}

int main(){
    work();
    return 0;
}