AcWing 5562. 最大生产-二分!
原题链接
中等
作者:
MuQY
,
2024-03-30 21:46:00
,
所有人可见
,
阅读 12
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
ll n, k;
ll a[N], b[N];
bool check(ll mid)
{
ll cnt = k;
for (int i = 1; i <= n; i++)
{
if (b[i] / a[i] >= mid)//够用
continue;
else//不够用
{
cnt -= a[i] * mid - b[i];
if(cnt < 0) return false;
}
}
return true;
}
int main()
{
cin >> n >> k;
ll sum = 0;
ll min_a = 0x3f3f3f3f;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 1; i <= n; i++){
cin >> b[i];
sum += b[i] / a[i];
}
sum += k;
// 二分
ll l = 0, r = 2e9;
ll mid = 0;
ll ans;
while (l <= r)
{
mid = l + (r - l) / 2;
if (check(mid))
{ // 如果能生产这么多,则记录mid为ans
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans << endl;
return 0;
}