最大合金数

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int res = 0;

        int maxBound = *min_element(stock.begin(), stock.end()) + budget;

        for (auto& comp: composition) {
            auto check = [&](long long num) -> bool {
                long long money = 0;
                for (int i = 0; i < n; i++) {
                    if (stock[i] < comp[i] * num) {
                        money += (comp[i] * num - stock[i]) * cost[i];
                        if (money > budget) {
                            return false;
                        }
                    }
                }
                return true;
            };

            int left = res, right = maxBound + 1;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (check(mid)) left = mid;
                else right = mid;
            }
            res = left;
        }
        return res;
    }
};