洛谷 二分搜索算法官方题单 个人题解 持续更新

第一题 查找

#include
using namespace std;
const int N=1e6+10;
int a[N];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i> a[i];
    }
    while(m--){
        int q;
        cin >> q;
        int l=0,r=n-1;
        while(l> 1;
            if(a[mid] 
第2题 A-B数对
 
#include
typedef long long ll;
using namespace std;
ll n,c,cnt;
const int N=2e5+10;
ll a[N];
mapm;
int main(){
    cin >> n >> c;
    for(ll i=0;i> a[i];
        m[a[i]]++;
    }
    sort(a,a+n);
    for(ll i=0;i>1;
            if(a[mid]>=a[i]+c){
                r=mid;
            }
            else {
                l=mid+1;
            }
        }
        if(a[l]-a[i]==c){
            cnt+=m[a[l]];
        }
    }
    cout << cnt;
    return 0;
 }
 
第三题 一元三次方程
 
#include
using namespace std;
double a,b,c,d;
int cnt;
mapm;
double f(double x){
    return a*x*x*x+b*x*x+c*x+d;
}
double ef(double l,double r){
    while(l -r > 1e-6 || r-l >1e-6){
        double mid = (l+r)/2;
        if(f(l)*f(mid)<=0){
            r=mid;
        }
        else {
            l=mid;
        }
    }
   // cout << l << " " << endl;
    cnt++;
    return r;
}
int main(){
    double ans;
    cin >> a >> b >> c >> d;
    for(double i=-100;i<100;i++){
        
        double l=i,r=i+1;
        if(f(l)==0){
            printf("%.2lf ",l);
            cnt++;
        }
      //  cout << f(l) <<" "<< f(r) << endl;
        if(f(l)*f(r)<0){
           // cout << "hello";
            ans=ef(l,r);
            
            printf("%.2lf ",ans);
            
        }
        //printf("%.2lf ",ans);
        
        if(cnt==3){
            break;
        }
    }
    
    return 0;
}
 
第四题 烦恼的高考志愿
 
#include
typedef long long ll;
using namespace std;
ll n,m,sum;
int an[100010],am[100010];
int main(){
    cin >> n >> m;
    for(int i=0;i> an[i];  //school
    }
    for(int j=0;j> am[j]; //xuesheng
    }
    sort(an,an+n);
   // for(int i=0;i>1;
            if(an[mid]<=am[i]){ //找到的是小于等于这个值的所有值中的最大值
                l=mid;
            }
            else {
                r=mid-1;
            }
        }
        //cout << am[i]<<" " <
       
        if(am[i]-an[l]>0){
            if(an[l+1]==0){
                tmp=am[i]-an[l];
            }
            else {tmp=min(am[i]-an[l],an[l+1]-am[i]);}
        }
        else {
            tmp=an[l]-am[i];
        }
        sum+=tmp;
    }
    cout << sum;
    return 0; 
}
 
第五题 砍树
 
#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll a[N];
ll n,m;
bool check(ll mid){
    ll sum=0;
    for(int i=0;i> n >> m;  
    ll tree=0;
    for(int i=0;i> a[i];
        tree=max(a[i],tree);
    }
    sort(a,a+n);
    ll l=0,r=tree;
    while(l> 1;
        if(check(mid)){
            r=mid-1;
        }
        else {
            l=mid;
        }
    }
    cout << l ;
    return 0;
}
 
木材加工
 
#include
using namespace std;
int n,k;
int a[100010];
int mx,mn=1e9,sum;
long long cnt=0;
bool check(int x){
    sum=0;
    for(int i=0;i=k){  //说明小木块的长度可以取更长一点
        return true;
    }
    else {
        return false;
    }
}
int main(){
    cin >> n >> k;
    for(int i=0;i> a[i];
        mx=max(a[i],mx);
        cnt+=a[i];
    }
    int l=1,r=mx;
    while(l> 1;
      //  cout << mid << endl;
        if(check(mid)){
            l=mid;
        }
        else {
            r=mid-1;
        }
    }
    if(cnt 
跳石头
 
#include
using namespace std;
int lg,n,m;
int a[50010],b[50010],c[50010];
int mx;
bool check(int x){
    int tmp=m;
    c[0]=0;
    for(int i=1;i<=n+1;i++){
        c[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=n+1;i++){
        if(c[i]> lg >> n >> m;
    a[0]=b[0]=0,a[n+1]=lg;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        mx=max(a[i]-a[i-1],mx);
    }
    for(int i=1;i<=n+1;i++){
        b[i]=a[i]-a[i-1];
    }
    mx=max(a[n+1]-a[n],mx);
    int l=0,r=lg;
    while(l> 1;
        if(check(mid)){
            l=mid;
        }
        else {
            r=mid-1;
        }
    }
    cout << l  ;
    return 0;
}
 
路标设置
 
#include
using namespace std;
int lg,n,k;
int a[100010],b[100010];
bool check(int x){ //枚举所有相邻旗子之间的距离，如果距离大于空旷指数了，看看此地需要多少面旗子，就插多少面
    int cnt=0;
    for(int i=0;ix){
            if((a[i+1]-a[i])%x==0){
                cnt+=(a[i+1]-a[i])/x-1;
            }
            else {cnt+=(a[i+1]-a[i])/x;}
        }
    }
    if(cnt<=k){  //说明插的旗子少了，空旷指数可以再小一点 
        return true;
    }
    else {
        return false;
    }
}
//我们二分空旷指数及绿色部分的最小值，看达到这个空旷指数需要插多少次旗，
int main(){
    cin >>lg >> n >> k;
    for(int i=0;i> a[i];
    }
    int l=0,r=lg;
    while(l> 1;
        if(check(mid)){
            r=mid;
        }
        else {
            l=mid+1;
        }
    }
    cout << l;
    return 0;
}