2861. 最大合金数

leetcode
2.9k words

https://leetcode.cn/problems/maximum-number-of-alloys/description/

解答

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
class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int stock_max = 0;
        for (int i = 0; i < stock.size(); ++i) {
            stock_max = max(stock_max, stock[i]);
        }
        int left = 1, right = max(0, budget + stock_max), ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            bool valid = false;
            for (int i = 0; i < k; ++i) {
                long long spend = 0;
                for (int j = 0; j < n; ++j) {
                    spend += max(static_cast<long long>(composition[i][j]) * mid - stock[j], 0LL) * cost[j];
                }
                if (spend <= budget) {
                    valid = true;
                    break;
                }
            }
            if (valid) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

解释

好的，我将按照您的要求，结合代码块逐段进行解释。

  1. 函数定义和参数说明：

    1
    2
    3
    class Solution {
    public:
        int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {

    这段代码定义了一个名为maxNumberOfAlloys的函数，属于Solution类。它接收六个参数：n表示不同金属的数量，k表示可以制作的不同合金组合的数量，budget是生产合金的总预算，composition是一个二维向量，每一行代表一种合金的组成，每一列代表制作该合金所需的特定金属的数量，stock是一个向量，表示每种金属的现有库存，cost是一个向量，表示每种金属的单位成本。

  2. 二分查找初始化：

    1
    2
    int left = 1, right = 2e8, ans = 0;
    while (left <= right) {

    这里初始化了二分查找的左右边界left和right，以及最终答案ans。二分查找的目的是在预算范围内找出能生产的最大合金单位数。left初始化为1，right初始化为2e8（即200,000,000），表示可能的合金单位数的搜索范围。然后，使用while循环进行二分查找。

  3. 计算中间值并检查是否有效：

    1
    2
    3
    int mid = (left + right) / 2;
    bool valid = false;
    for (int i = 0; i < k; ++i) {

    在每次循环中，首先计算中间值mid，这代表当前考虑的合金单位数。然后，使用一个布尔变量valid来标记是否能在预算内生产mid单位的任何合金。

  4. 计算生产特定合金所需的成本：

    1
    2
    3
    4
    5
    6
    7
    8
    long long spend = 0;
    for (int j = 0; j < n; ++j) {
        spend += max(static_cast<long long>(composition[i][j]) * mid - stock[j], 0LL) * cost[j];
    }
    if (spend <= budget) {
        valid = true;
        break;
    }

    对于每种合金（通过外层循环遍历），计算生产mid单位所需的总成本。内层循环遍历所有金属，计算每种金属的额外需求量和成本（如果已有库存足够，则不需要额外购买）。如果某种合金的生产总成本不超过预算，则将valid设为true并跳出循环。

  5. 更新二分查找的边界：

    1
    2
    3
    4
    5
    6
    if (valid) {
        ans = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }

    如果找到了一个有效的解（即在预算内可以生产mid单位的合金），则更新答案ans为mid，并将搜索范围调整为更高的合金单位数（即left = mid + 1）。否则，减小搜索范围，探索更少的合金单位数（即right = mid - 1）。

  6. 返回结果：

    1
    2
    3
    return ans;
    }
    };

    一旦完成了二分查找，函数返回ans，它是在给定预算内可以生产的最大合金单位数。这是二分查找算法的典型应用，用于在预定义的搜索范围内找到满足特定条件的最优解。

    关键步骤

1
spend += max(static_cast<long long>(composition[i][j]) * mid - stock[j], 0LL) * cost[j];

这行代码是核心部分之一，用于计算生产一定数量(mid)的某种合金(i)所需的总成本。让我们逐步解析这行代码：

  1. composition[i][j]: 这部分表示制作第i种合金所需第j种金属的数量。composition是一个二维向量，其中每一行代表一种合金的组成，每一列代表一种特定金属。

  2. static_cast<long long>(composition[i][j]) * mid: 这里将第i种合金的第j种金属的需求量乘以我们想要生产的合金单位数(mid)。由于这个乘法可能导致整数溢出，因此使用static_cast<long long>将其转换为长整型(long long)，以确保计算的准确性。

  3. - stock[j]: 从上一步得到的总需求量中减去当前库存(stock[j])中已有的第j种金属的数量。如果库存足够，这个值可能是负数或零。

  4. max(..., 0LL): 使用max函数确保计算的结果不会小于零。如果上一步的结果是负数或零，意味着不需要额外购买这种金属，因此这个表达式的结果将是零。

  5. * cost[j]: 将上述得到的额外需求量（如果有的话）乘以第j种金属的单位成本(cost[j])。这给出了购买所需额外金属的总成本。

  6. spend += ...: 将为第i种合金的每种金属计算出的成本累加到变量spend中。spend代表生产mid单位的第i种合金所需的总成本。

综上所述，这行代码的作用是计算并累加生产特定数量的某种合金所需购买的每种金属的成本，考虑到库存中已有的量，从而确保不会超出预算。

Comments