优秀地方门户网站系统,长网址变成短网址,盐城市亭湖区城乡建设网站,梧州论坛最新消息2861. 最大合金数
难度#xff1a; 中等
题目大意#xff1a; 假设你是一家合金制造公司的老板#xff0c;你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用#xff0c;并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建…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, k 1000 budget 10^8composition.length kcomposition[i].length n1 composition[i][j] 100stock.length cost.length n0 stock[i] 10^81 cost[i] 100 示例 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 份合金。分析
本题难度主要在理解题的意思变量有点多可能容易晕类似什么最值我们首先可以考虑用二分法这题显然是可以用的单调性是 合金越多要的钱就越多合金越少那么所需要的钱就是足够的所以我们可以根据这个性质来进行二分
二分答案
class Solution {
public:using LL long long;int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost) {// mid 生产mid个合金u是选auto check [](int mid, int u) {LL left budget;for (int i 0; i n; i ) {if (stock[i] (LL)mid * composition[u][i]) continue; // 如果当前储存量够left - ((LL)mid * composition[u][i] - stock[i]) * cost[i];// 减去所需要的费用if (left 0) return false; // 如果不够了说明合金是做不出来的直接返回false}return true; // 如果没有什么问题就返回true};int res 0;for (int i 0; i k; i ) {int l 0, r 1e9; // 不能用1e8while (l r) {int mid l r 1 1;if (check(mid, i)) l mid;else r mid - 1;}res max(res, l);// 取一个最大值}return res;}
};时间复杂度 O ( n k l o g C ) O(n k logC) O(nklogC)
结束了
