为了让所有奶牛的牛蹄都能得到及时修剪,约翰计划向某工厂定制一批自动修蹄车。
制作一辆修蹄车需要用到 n种零件,其中第i种零件需要用ai个。
由于约翰对于修蹄车数量的需求是越多越好,所以工厂也希望制作出尽可能多的修蹄车以满足客户的需求。
已知,对于第i种零件,工厂的库存为 bi个。
此外,工厂中还有k个未加工原材料,每个原材料都可以被加工为一个任意种类的零件。
请你计算,利用现有的零件以及原材料,工厂最多可以生产出多少辆修蹄车。
输入格式
第一行包含两个整数 n,k。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含 n个整数 b1,b2,…,bn。
输出格式
一个整数,表示可以生产的修蹄车的最大可能数量。
数据范围
前6个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105,1≤k≤109,1≤ai,bi≤109。
样例
1 1000000000
1
1000000000
输出样例
2000000000
算法1
二分(O(logn))
要解决这个问题,我们可以采用二分搜索法来找到最多可以生产的修蹄车数量基本思路是,我们尝试一个可能的修蹄车数量
x,如果我们现有的零件加上原材料不足以完成x个修蹄车,那么就二分更小一点的x。反之也一样。
为什么用二分:
我们设最大能生成x个车,当生产的车辆数<x时,额外所需要原材料数一定是<k的,当生产的车辆数>x时,一定是>k的,具有二段性,所以能够二分;
C++ 代码
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N];
int n,k;
bool check(ll x){
ll extra=0;// 计算生产x辆修蹄车还需要多少额外的零件
for(int i=0;i<n;i++){//需要的第i种零件总数 - 现有的第i种零件数量
extra+=max(0ll,a[i]*x-b[i]);
if(extra>k) return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++) scanf("%d",&b[i]);
ll l=0,r=1e10,mid;
while(l<r){//注意这里要用r=mid-1这个模版,因为当extra>k时,x一定取不到
//当extra<=k时,x可能是答案
mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d",r);
return 0;
}