2021长沙学院蓝桥杯训练赛3

B,D 二分

B题：二分找和尚

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n , ans , mx;
int t;

bool check(ll xiao  , ll da , ll m){
    ll s = xiao+9*m+(da-m) ;
    if(s<n){
        mx = max(mx,s);
        return true;
    } 
    return false;
}

void slove(){
    scanf("%lld",&n);
    if(n<=6) {
        cout<<"-1 -1"<<endl;
        return  ;
    }
    ll yu = n%3 , mi;
    if(yu==0) yu = 3;   //大小和尚不能为0
    ll da = (n-yu)/3 , xiao  = yu*3;
    mi = da+xiao;
    if(mi>=n) {
        cout<<"-1 -1"<<endl;
        return  ;
    }
    mx = mi;
    ll l = 0 , r = da;
    while(l<r){
        ll mid = l+r>>1;
        if(check(xiao , da , mid)) l = mid;
        else r = mid-1;
    }
    cout<<mx<<" "<<mi<<endl;
}
int main(){
    scanf("%d",&t);
    while(t--){
        slove();
    }
    return 0;
}

D题：二分找能量值，

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5; 
int n,a[N] , l , r;
int mx;
bool check(int x){
    for(int i=0;i<n;i++){
        if(x<=a[i]) x-=(a[i]-x);
        else x+=(x-a[i]); 
        if(x<0) return false;
                if(x>mx) return true;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        r = max(r,a[i]);
    }
    mx = r;
    while(l<r){
        int mid = l+r>>1;
        if(check(mid)) r=mid;
        else l = mid+1; 
    }
    cout<<l<<endl;
    return 0;
}