二分复习

二分板子

数的范围

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int n,q,k;
int a[N];

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

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

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(q--){
        cin>>k;
        int l=findL(k)-1;
        int r=findR(k)-1;
        if(!(l>=0 and l<n and r>=0 and r<n and a[l+1]==k and a[r+1]==k))cout<<"-1 -1"<<endl;
        else cout<<l<<" "<<r<<endl;
    }
}

数的三次方根

#include<bits/stdc++.h>
using namespace std;
const double N=100010;

int main(){
    double k;cin>>k;
    double l=-N,r=N;
    while(r-l>0.000000001){
        double mid=(l+r)/2;
        if(mid*mid*mid<=k)l=mid;
        else r=mid;
    }
    cout<<setiosflags(ios::fixed)<<setprecision(6)<<l<<endl;
    //  printf("%.6lf\n",l);
}

二分答案

聪明的质检员

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
typedef long long LL;
int n,m,w[N],v[N],l[N],r[N];
LL s,sn[N],sv[N],ans=1e18;

bool check(int W){
    memset(sn,0,sizeof sn);
    memset(sv,0,sizeof sv);
    for(int i=1;i<=n;i++){
        if(w[i]>=W)sn[i]=sn[i-1]+1,sv[i]=sv[i-1]+v[i];
        else sn[i]=sn[i-1],sv[i]=sv[i-1];
    }
    LL y=0;
    for(int i=1;i<=m;i++){
        y+=(sn[r[i]]-sn[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
    }
    ans=min(ans,abs(y-s));
    return y<=s;
}

LL find(){
    int l=0,r=1e6+1;
    while(l+1<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    return ans;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++)cin>>l[i]>>r[i];
    cout<<find()<<endl;
}