GitBook

这里写图片描述

题目大意:制作一个蛋糕需要n种材料,然后你有k克魔法粉,每克魔法粉可以代替任意一克的材料,ai代表制作一个蛋糕需要第i种材料多少克,bi代表你拥有第i个材料多少克,问做可以做多少个蛋糕。

判断能不能做mid个蛋糕 如果不能则减少mid的范围 以此二分查找

#include<stdio.h>
#include<algorithm>
using namespace std;
__int64 a[100200],b[100200];
__int64 n,k;
bool judge(__int64 x) {
	__int64 t=k;
	for(int i=0; i<n; i++) {
		if(b[i]+t>=a[i]*x)
			t-=max((__int64)0,a[i]*x-b[i]);
		else
			return false;
	}
	return true;
}
int main() {
	while(scanf("%I64d %I64d",&n,&k)!=EOF) {
		for(int i=0; i<n; i++)
			scanf("%I64d",&a[i]);
		for(int i=0; i<n; i++)
			scanf("%I64d",&b[i]);
		__int64 l=0,r=2000000002,res;
		while(l<=r) {
			__int64 mid=(l+r)/2;
			if(judge(mid)) {
				res=mid;
				l=mid+1;
			} else
				r=mid-1;
		}
		printf("%I64d\n",res);
	}
	return 0;
}

题目地址:【CodeForces】[670D2]Magic Powder - 2