题干

思路

所有合金都需要由同一台机器制造，因此我们可以枚举使用哪一台机器来制造合金。

对于每一台机器，我们可以使用二分查找的方法找出最大的整数 xxx，使得我们可以使用这台机器制造 xxx 份合金。找出所有 xxx 中的最大值即为答案。

代码

class Solution {public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {// 全部转成 int[] 数组，效率比 List<Integer> 更高int[] stocks = toArray(stock);int[] costs = toArray(cost);int ans = 0;for(List<Integer> c : composition)ans = calculate(budget, toArray(c), stocks, costs, ans);return ans;}//集合转换为数组private int[] toArray(List<Integer> list) {int[] arr = new int[list.size()];for(int i = 0; i < arr.length;i++)arr[i] = list.get(i);return arr;}//检查private boolean check(int budget, int[] compositions, int[] stocks, int[] costs, int count) {for(int i = 0; i < compositions.length; ++i) {int delta =  compositions[i] * count - stocks[i];if(delta <= 0) continue;budget -= delta * costs[i];if(budget < 0)return false;}return true;}//二分private int calculate(int budget, int[] compositions, int[] stocks,int[] costs, int count) {if(!check(budget, compositions, stocks, costs, count + 1))return count;count = count + 1;while(check(budget, compositions, stocks, costs, count << 1))count <<= 1;int left = count,  right = count << 1;while(left <= right) {int mid = left + right >> 1;if(check(budget, compositions, stocks, costs, mid)) left = mid + 1;else right = mid - 1;}return right;}	
}