网站建设实施进度与资源管理,百度关键词推广可以自己做吗,wordpress首页调用指定分类,主题网站开发报告文章目录 Tag题目来源解题思路方法一#xff1a;二分枚举答案 写在最后 Tag
【二分枚举答案】【数组】【2024-01-27】 题目来源
2861. 最大合金数 解题思路
方法一#xff1a;二分枚举答案
思路
如果我们可以制造 x 块合金#xff0c;那么一定也可以制造 x-1 块合金。于… 文章目录 Tag题目来源解题思路方法一二分枚举答案 写在最后 Tag
【二分枚举答案】【数组】【2024-01-27】 题目来源
2861. 最大合金数 解题思路
方法一二分枚举答案
思路
如果我们可以制造 x 块合金那么一定也可以制造 x-1 块合金。于是我们可以枚举可以制造的合金数量
设 mid 为当前二分的答案如果可以在预算范围内可以制造 mid 块合金那么更新二分范围的左边界表示可以制造的合金可以再多一些如果不能在预算范围内制造 mid 块合金那么更新二分范围的右边界。
那么当我们二分到 mid 时如何判断是否可以制造 mid 块合金呢
题目中有一条重要信息「所有合金都需要由同一台机器制造」换言之如果使用某一台机器加工合金那么其他所有合金都要由这台机器加工中途不同换别的机器。于是我们可以枚举使用哪一台机器。对于使用第 i 台机器加工第 j 种合金需要的金属为 c o m p o s i t i o n [ i ] [ j ] × m i d composition[i][j] \times mid composition[i][j]×mid当前已经拥有的金属数量为 s t o c k [ j ] stock[j] stock[j]因此还需要的预算为 s p e n d m a x c o m p o s i t i o n [ i ] [ j ] × m i d , 0 × c o s t [ j ] spend max{composition[i][j] \times mid, 0} \times cost[j] spendmaxcomposition[i][j]×mid,0×cost[j]
如果 spend budget 则可以在预算范围内可以制造 mid 块合金否则不可以。
二分查找的上下限如何确定
二分查找的下界可以设置为 0 或者 1这取决于二分区间的开闭形式这里二分的下界我设定为 0表示可以加工的合金数最大值可以为 0。当然可以设置下界为 1但是这时候的需要维护一个额外的变量 res 记录答案并且初始化 res 0。
可以假设 composition[i][j] 和 cost[j] 都是 1这样就可以计算出二分查找的上界为 min(stock) budget。
关于二分查找的开闭形式这篇文章 讲的比较清楚可以参考。
算法
class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost) {int left 0, right ranges::min(stock) budget;while (left right) { // 二分的闭区间写法int mid left ((right - left) 1);bool isValid false;for (int i 0; i k; i) {long long spend 0;for (int j 0; j n; j) {spend max(static_castlong long(composition[i][j]) * mid - stock[j], 0LL) * cost[j];}if (spend budget) {isValid true;break;}}if (isValid) {left mid 1;}else {right mid - 1;}}return left-1;}
};复杂度分析
时间复杂度 O ( k n l o g U ) O(knlogU) O(knlogU) U m i n ( s t o c k ) b u d g e t U min(stock) budget Umin(stock)budget。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
