A21371. 制作蛋糕（cake.cpp）
填空题
中等
知识点
题目描述
制作蛋糕（cake.cpp）
题目描述
圣诞节联欢活动有制作蛋糕环节。每个同学获得 n 种食材（编号 1~n），第 i 种食材的量为 bᵢ克，另有 k 克万能粉（1 克万能粉可代替 1 克任意食材）。制作一个蛋糕需要第 i 种食材 aᵢ克（必须使用所有食材），求最多能制作的蛋糕个数。
输入描述
第一行包含两个正整数 n 和 k（1≤n≤1e5，1≤k≤1e3）；第二行包含 n 个整数 a₁、a₂、…、aₙ（1≤aᵢ≤1e3），表示每个蛋糕所需第 i 种食材的量；第三行包含 n 个整数 b₁、b₂、…、bₙ（1≤bᵢ≤1e3），表示每个同学获得第 i 种食材的量。
输出描述
输出最多能制作的蛋糕个数。
样例输入1
1 1000000000
1
1000000000样例输出1
2000000000样例输入2
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1样例输出2
0样例输入3
3 1
2 1 4
11 3 16样例输出3
4样例输入4
4 3
4 3 5 6
11 12 14 20样例输出4
3参考答案
include <bits/stdc++.h>
usingnamespacestd;
constint MAXN = 100001; // 适配n≤1e5的范围
longlong a[MAXN], b[MAXN]; // 用long long避免溢出
longlong n, k;
// 检查制作x个蛋糕是否可行
bool check(long long x) {
longlong need = 0; // 总缺口
for (int i = 1; i <= n; ++i) {
// 计算第i种食材的缺口：需求(x*a[i]) - 已有(b[i])，缺口不能为负
longlong gap = max(0LL, x * a[i] - b[i]);
need += gap;
// 提前剪枝：总缺口超过k则直接返回不可行
if (need > k) {
returnfalse;
}
}
return need <= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i]; // 每个蛋糕需要的第i种食材量
}
for (int i = 1; i <= n; ++i) {
cin >> b[i]; // 初始拥有的第i种食材量
}
// 二分查找的边界：左边界0，右边界取足够大的值（比如1e14）
longlong l = 0, r = 2e14;
longlong ans = 0;
while (l <= r) {
longlong mid = (l + r) / 2;
if (check(mid)) {
// mid可行，尝试更大的数
ans = mid;
l = mid + 1;
} else {
// mid不可行，尝试更小的数
r = mid - 1;
}
}
cout << ans << endl;
return0;
}
上一题
下一题