蓝桥杯2022年第十三届决赛真题-卡牌 简单二分

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll N=2e5+5;
struct node{
    ll a,b;
}k[N];
ll n,m,t[N];
bool coke(ll x){
    ll ans=0;
    memset(t,0,sizeof t);
    for(ll i=1;i<=n;i++){
        if(k[i].a<x){t[i]+=x-k[i].a;ans+=x-k[i].a;}
        if(t[i]>k[i].b)return false;//超过第 i 种牌最多次数
    }
    return ans<=m;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++)cin>>k[i].a;
    for(ll i=1;i<=n;i++)cin>>k[i].b;
    ll l=-1,r=1e9;
    while(l+1<r){
        ll mid=l+r>>1;
        if(coke(mid))l=mid;
        else r=mid;
    }
    cout<<l<<endl;
    return 0;
}