DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

交付肥料

返回题目

题解

合成 ttt 批可得到 2t2t2t 桶氨,因此最少需要合成 t=⌈K/2⌉t=\lceil K/2\rceilt=⌈K/2⌉ 批。增加批数需要更多原料,不会降低费用。只需分别求购买 ttt 单位氮气和 3t3t3t 单位氢气的最小费用。

对任一种原料,都应先从每桶价格较低的供应商处购买。如果从较贵的供应商处购买了一桶,且较便宜的供应商还有库存,则可以改从较便宜的供应商处购买这一桶。总数量不变,费用降低。每桶价格相同的供应商的顺序不影响费用。因此按价格升序排序,每次购买库存量与剩余需求量两者中的较小值。如果任一种原料的总库存不足,则输出 -1。

设 M=kn+khM=k_n+k_hM=kn​+kh​,时间复杂度为 O(Mlog⁡M)O(M\log M)O(,空间复杂度为 。采购总量为 单位,每桶价格至多为 ,因此有解时答案的最大值为 。

Solution written by GPT

M
log
M
)
O(M)O(M)O(M)
4t≤2⋅1094t\leq 2\cdot 10^94t≤2⋅109
10610^6106
2⋅10152\cdot 10^{15}2⋅1015