Leetcode 2861 最大合金数 // 洛七的摸鱼池塘

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 <= 100
0 <= budget <= 10^8
composition.length == k
composition[i].length == n
1 <= composition[i][j] <= 100
stock.length == cost.length == n
0 <= stock[i] <= 10^8
1 <= cost[i] <= 100

解答

本题的难度是 Medium.

我直接暴力算法, 从第一个机器开始, 判断最大的合金数是多少, 然后第二个机器看看能不能超过前一个, 以此类推.

代码如下:

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int result = 0;
        int temp;
        int resultIndex = 0;
        for (int i = 0; i < k; i++) {
            temp = result;
            List<Integer> perIron = composition.get(i);
            // 假设可以做 j 份合金
            for (int j = result+1; ; j++) {

                // 做 j 份需要 perIron *j
                // 除去库存还需要 perIron * j - stock
                int[] need = new int[n];
                for (int l = 0; l < n; l++) {
                    need[l] = Math.max(0,perIron.get(l) * j - stock.get(l));
                }
                int needCost = getCost(need, cost);
                if(needCost > budget || needCost<0){
                    temp = j-1;
                    break;
                }
            }
            if (temp > result) {result = temp;resultIndex = i;}
        }
        return result;
    }

    private int getCost(int[] need, List<Integer> cost){
        int result = 0;
        for (int i = 0; i < need.length; i++) {
            result += need[i] * cost.get(i);
        }
        return result;
    }
}

这个代码最后超时了, 其实就算不超时也很抽象,因为有些地方会直接越界, 所以导致我有些地方的判断很抽象, 可能会出现需要额外开销的是负的.
这也正常,时间复杂度为 O(nkC), 其中这个 C 是答案的范围,那么可能你会奇怪,题目怎么提示是二分呢? 这也明明没用到二分啊,这就是为什么我超时了, 而使用二分的话可能可以将其中一个转为 O(log), 很明显的, 因为 n 和 k 的最大值都不超过100, 转化为 O(logn) 时间效率其实差的不是特别多, 因此考虑 C, 我超时的那个样例可以制作的合金数为 77472690, 相当于是我们考虑对于制作 m 个合金, 能否存在满足预算,如果可以就增加考虑的合金数量. 因此我们这边要先考虑合金数量的上下界.
我们考虑极端情况, 当消耗为 1, stock = 10^8, 且 budget 为 10^8 时, 那我们最多可以做 2*10^8 个合金.
因此我们设置上界为 2*10^8, 下界为 0, 因为可能一个都做不了嘛, 因此以合金可能的数量为界, 然后做二分

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int left =0, right = 200000000, result = 0;
        int mid;
        boolean flag;
        long needCost = 0;
        while(left <= right){
            mid = (left+right) / 2;
            flag = false;
            for (int i = 0; i < k; i++) {
                needCost = 0;
                for (int j = 0; j < n; j++) {
                    needCost += Math.max((long) composition.get(i).get(j) * mid -stock.get(j),0) * cost.get(j);
                }
                if (needCost <= budget){
                    // 表示在右边
                    flag = true;
                    break;
                }
            }
            if (flag){
                result = mid;
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return result;
    }
}

只能击败 6.90%, 感觉是 List 的锅, 修改看看, cost 去掉变 11.72%, stock 去掉变 19.31%, 再改 composition :

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int left =0, right = 200000000, result = 0;
        int mid;
        boolean flag;
        long needCost = 0;
        int[] costInt = cost.stream().mapToInt(Integer::intValue).toArray();
        int[] stockInt = stock.stream().mapToInt(Integer::intValue).toArray();
        int[][] compositionInt = new int[k][n];
        for (int i = 0; i < k; i++) {
            compositionInt[i] = composition.get(i).stream().mapToInt(Integer::intValue).toArray();
        }
        while(left <= right){
            mid = (left+right) / 2;
            flag = false;
            for (int i = 0; i < k; i++) {
                needCost = 0;
                for (int j = 0; j < n; j++) {
                    needCost += Math.max((long) compositionInt[i][j] * mid -stockInt[j],0) * costInt[j];
                }
                if (needCost <= budget){
                    // 表示在右边
                    flag = true;
                    break;
                }
            }
            if (flag){
                result = mid;
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return result;
    }
}

时间效率直接提升到 75.86%, 感觉还是怪怪的, 可能还是得根据具体情况生成上界. 我这里用 2*10^8 是题目的上限, 我们可以根据当前样例生成上限

int[] stockInt = stock.stream().mapToInt(Integer::intValue).toArray();
int right = budget + Arrays.stream(stockInt).max().getAsInt();

范围变成了 [0, budget+max(stock)], 但是试了一下, 没差, 因为本来就是 O(logC), 稍微降低一点 C, 但是需要增加从 stock 中找最大值的步骤, 所以一增一减, 导致没差.