临夏市做网站电话,免费建设自己的文学网站,互联网信息服务,wordpress建站需要学什么大家好#xff0c;我是星恒#xff0c;今天给大家带来的是一道比较正常的二分题目 题目#xff1a;leetcode 2861假设你是一家合金制造公司的老板#xff0c;你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用#xff0c;并且你可以使用 k 台机器来制… 大家好我是星恒今天给大家带来的是一道比较正常的二分题目 题目leetcode 2861假设你是一家合金制造公司的老板你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。对于第 i 台机器而言创建合金需要 composition[i][j] 份 j 类型金属。最初你拥有 stock[i] 份 i 类型金属而每购入一份 i 类型金属需要花费 cost[i] 的金钱。给你整数 n、k、budget下标从 1 开始的二维数组 composition两个下标从 1 开始的数组 stock 和 cost请你在预算不超过 budget 金钱的前提下最大化 公司制造合金的数量。所有合金都需要由同一台机器制造。返回公司可以制造的最大合金数。 示例 示例 1
输入n 3, k 2, budget 15, composition [[1,1,1],[1,1,10]], stock [0,0,0], cost [1,2,3]
输出2
解释最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金我们需要购买
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 * 1 2 * 2 2 * 3 12 的金钱小于等于预算 15 。
注意我们最开始时候没有任何一类金属所以必须买齐所有需要的金属。
可以证明在示例条件下最多可以制造 2 份合金。示例 2
输入n 3, k 2, budget 15, composition [[1,1,1],[1,1,10]], stock [0,0,100], cost [1,2,3]
输出5
解释最优的方法是使用第 2 台机器来制造合金。
要想制造 5 份合金我们需要购买
- 5 份第 1 类金属。
- 5 份第 2 类金属。
- 0 份第 3 类金属。
总共需要 5 * 1 5 * 2 0 * 3 15 的金钱小于等于预算 15 。
可以证明在示例条件下最多可以制造 5 份合金。示例 3
输入n 2, k 3, budget 10, composition [[2,1],[1,2],[1,1]], stock [1,1], cost [5,5]
输出2
解释最优的方法是使用第 3 台机器来制造合金。
要想制造 2 份合金我们需要购买
- 1 份第 1 类金属。
- 1 份第 2 类金属。
总共需要 1 * 5 1 * 5 10 的金钱小于等于预算 10 。
可以证明在示例条件下最多可以制造 2 份合金。提示
1 n, k 1000 budget 108composition.length kcomposition[i].length n1 composition[i][j] 100stock.length cost.length n0 stock[i] 1081 cost[i] 100
分析这道题的思路是二分。因为制造数的范围是有限的是10^8 所以我们可以遍历可以制造数量的最大数利用二分来优化遍历使用的机器当使用这个数量制造金属时是否会超过预算。这样我们就可以遍历到需要的金属最大数。
这确实是很优质的解法我们来看看我们的暴力求解。乍一看这道题是让我们选择对机器然后计算能制造的金属数。对于确定使用的机器我们并没有什么好方法我们只能通过遍历比较哪台机器在budget下的制造的数量最多来侧面反应出哪个机器最多这也是计算机的擅长的事。我们来分析一下他的时间复杂度遍历每一种机器为n遍历最大金数数(budget/cost)计算一份合金所需花费k。总的时间复杂度O(n * (k budget/cost))
题解
class Solution {public int maxNumberOfAlloys(int n, int k, int budget, ListListInteger composition, ListInteger stock, ListInteger cost) {int left 1, right 200000000, ans 0;while (left right) {int mid (left right) / 2;boolean valid false;for (int i 0; i k; i) {long spend 0;for (int j 0; j n; j) {spend Math.max((long) composition.get(i).get(j) * mid - stock.get(j), 0) * cost.get(j);}if (spend budget) {valid true;break;}}if (valid) {ans mid;left mid 1;} else {right mid - 1;}}return ans;}
}时间复杂度O(nklogC)
如果大家有什么思考和问题可以在评论区讨论也可以私信我很乐意为大家效劳。好啦今天的每日一题到这里就结束了如果大家觉得有用可以可以给我一个小小的赞呢我们下期再见
