当前位置:   article > 正文

LeetCode.2861. 最大合金数

LeetCode.2861. 最大合金数

题目

题目链接

分析

这道题目一定要多读几遍,才能理解。

大意就是你有钱budget 和 库存stock的金属零件,让你从一堆机器里面选择一种机器可以合成最多金属的数量是多少,这些机器合成金属需要的零件数目是不一样的,composition 数组给你了每个机器合成金属需要的零件数量,而且你还有每个零件的库存 stock 数组,当然你可以买合成金属需要的零件,每个零件的需要的金钱cost数组,但是你只有 budget 钱,问:使用其中的某台机器,能合成金属的最大数量。

这道题目有一个很重要的点就是:所有合金都需要由同一台机器制造。这个非常非常非常重要。

  • 合金数量越多,价格就越高,具有一定的单调性。适合二分查找。假设可以合成的金属的最大数量为 x,则一定可以制造小于 x 数量的金属,并且一定不能制造大于 x的金属。
  • 一般二分查找需要一个low,一个 high,我们这道题目,做少能合成金属数目就是0即low= 0,最大能合成金属的数目你可以直接使用 Integer.MAX_VALUE。或者你也可以缩小一个 high 的大小,我们可以假设合成金属需要的每个零件需要1,那么我们库存能合成的金属数量就是 Collections.min(stock),我们钱可以买的零件最大值就是每个零件只需要1,所以能买零件合成合金的数量为 budget ,所以 high 你也可以初始值为 high = Collections.min(stock) + budget;
  • 我们的low,high区间采用的是 [low,high],左闭右闭区间,这点很重要哦,对于我们后面 low和 high的移动很重要。
  • 因为二分,所以出现判断中间位置 target = left + (high - low) / 2;
  • 接下来就是判断所有机器是否存在一台机器可以合成 target 数量的金属了,方法如下:分别计算每台机器制造 target 数量的合金的总预算,如果存在一台机器能制造 target 的合金,就代表可以制造出 target 份合金,先把这个数字记录下来,在接着判断还能不能合成更大数量的合金,left = targrt + 1;否则则不能制造 target 份合金,high = target - 1;
  • 接下来的问题就是如何判断你手上的库存加上你手上的钱,是否存在一台机器能制造 target 数量的合金,这个方法如下:计算一下每台机器需要合成target数量的合金需要的钱,然后跟我们现有的钱进行比较,如果小于等于,代表存在一台机器能制造target数量的合金。
  • 接下来的问题就是如何知道每台机器合成target数量合金的时候需要的金钱。遍历composition 可以得到每台机器machine,遍历machine可以得到每台机器需要的零件数量,零件i已有的数量 stock[i],要合成target数量的合金需要购买零件i的数量additional = Math.max((long) machine.get(i) * target - stock.get(i),0);购买零件 i 需要的钱 additional * const.get(i),累加当前机器买每个零件需要的钱 totalCoins ,如果这个数字 小于等于 你有的钱budget,才继续遍历,遍历完当前机器machine所需要购买零件,得到总需要的钱 totalCoins 和 budget比较,小于等于就返回 true,代表这批机器存在一台能合成target数量的合金。

代码

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int low = 0, high = Collections.min(stock) + budget;
        // [low,high] :区间为左闭右闭
        int res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if(isPossible(n,budget,composition,stock,cost,mid)) {
                // 当前 mid 数量的合金机器可以合成 ,记录下来
                res = mid;
                low = mid + 1;
            }else {
                high = mid - 1;
            }
        }
        return res;
    }

    // 所有机器能不能制造 target 数量的合金
    public boolean isPossible(int n,int budget,List<List<Integer>> composition,List<Integer> stock,List<Integer> cost,int target) {
        // 遍历所有机器
        for(List<Integer> machine: composition) {
            // 当前机器合成 target 数量的合金需要的金钱总和
            long totalCoins = 0;
            for(int i = 0;i < n && totalCoins <= budget ;i ++) {
                // 当前机器合成 target 数量的合金需要购买的 零件i 的数量
                long additional = Math.max((long)machine.get(i) * target - stock.get(i),0);
                totalCoins += additional * cost.get(i);
            }
            if(totalCoins <= budget) {
                return true;
            }
        }
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码创新者/article/detail/60458
推荐阅读
相关标签
  

闽ICP备14008679号