2861.最大合金数

/*
 * @lc app=leetcode.cn id=2861 lang=typescript
 *
 * [2861] 最大合金数
 */

// 注意：所有机器的配方，都是生产同一种合金！！

// @lc code=start
function maxNumberOfAlloys(
	n: number, // 金属种类
	k: number, // 机器数量
	budget: number, // 预算金额
	composition: number[][], // 第i台机器制作1个合金需要j个金属
	stock: number[], // 拥有stock[x]份x金属
	cost: number[], // 购入一个x金属需要花费cost[x]金额
): number {
	let result = 0;
	composition.map(comp => {
		// 一台机器一台机器的计算
		let l = 0,
			r = Number.MAX_VALUE; // 定义左右边界
		while (l < r) {
			let mid = Math.ceil((l + r) / 2); // 向上取整
			let totalCost = 0; // 当前机器制作合金总花费
			for (let j = 0; j < n; j++) {
				// 循环每一种金属
				const need = comp[j] * mid;
				const haved = stock[j];
				const diff = need - haved; // 计算缺口
				if (diff > 0) {
					// 有缺口，需要购买
					totalCost += diff * cost[j];
				}
			}

			if (totalCost > budget) {
				// 超出预算了，缩小合金数量
				r = mid - 1;
			} else {
				// 还可以尝试生产更多合金，l变大
				l = mid;
			}
		}
		// l为最终可生产的合金数量
		result = Math.max(result, l);
	});
	return result;
}

// test
let n = 3,
	k = 2,
	budget = 15,
	composition = [
		[1, 1, 1],
		[1, 1, 10],
	],
	stock = [0, 0, 0],
	cost = [1, 2, 3];

console.log(
	"最多可生产：",
	maxNumberOfAlloys(n, k, budget, composition, stock, cost),
);

// 防止ts其余文件同名变量报错
export default {};
// @lc code=end