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