AcWing 5562. 最大生产 二分
原题链接
中等
作者:
一塌糊涂
,
2024-04-06 15:02:15
,
所有人可见
,
阅读 4
cpp 二分
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int n,k;
bool check(long long mid) {
//long long tmp = k;
long long tmp = 0 ;
for(int i=1;i<=n;i++) {
/*
这样判断就错了,因为库存的材料 只能用于这一种
if( a[i]*mid > (long long) b[i] + tmp) return false;
tmp = tmp+b[i] - (long long)a[i]*mid;
*/
tmp += max(0ll,mid*a[i] - b[i]);
if(tmp > k) return false;
}
return true;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
long long l = 0,r = 2e9;
while(l<r) {
long long mid = (l+r+1)>>1;
if(check(mid)) l=mid;
else r = mid-1;
}
cout<<l<<endl;
return 0;
}