二分查找练习题

卡牌

题目链接：卡牌

tips:

1. 记得开long long （最好把所有的数据都从 int 变成 long long）

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

const int N = 1e6+10;
const int MAX = 1e11;

typedef long long LL;

LL n,m,a[N],b[N];

//mid为能凑出的牌的套数
//m是全局变量，而每次判断 mid 是否满足条件时都要用到总空白牌数m这个值，因此 要用一个变量去代替 m 去操作 
bool check(int mid){
  LL sum = m;
  for(int i=1;i<=n;i++){
    if(a[i] >= mid) continue;
    if(b[i]+a[i] < mid || sum+a[i] < mid) return false;
    sum = sum - (mid - a[i]); 
  }
  if(sum < 0) return false;
  else{
    return true;
  }
}
int main()
{
  cin >> n >> m;
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  for(int i=1;i<=n;i++){
    cin >> b[i];
  }
  LL l = 0, r = INT_MAX; 
  while(l<r){
    LL mid = (l+r+1) / 2;
    if(check(mid)){
      l = mid;
    }
    else{
      r = mid-1;
    }
  }
  cout << l;
  return 0;
}