合成 批可得到 桶氨,因此最少需要合成 批。增加批数需要更多原料,不会降低费用。只需分别求购买 单位氮气和 单位氢气的最小费用。
对任一种原料,都应先从每桶价格较低的供应商处购买。如果从较贵的供应商处购买了一桶,且较便宜的供应商还有库存,则可以改从较便宜的供应商处购买这一桶。总数量不变,费用降低。每桶价格相同的供应商的顺序不影响费用。因此按价格升序排序,每次购买库存量与剩余需求量两者中的较小值。如果任一种原料的总库存不足,则输出 -1。
设 ,时间复杂度为 ,空间复杂度为 。采购总量为 单位,每桶价格至多为 ,因此有解时答案的最大值为 。
Solution written by GPT