回の合成でアンモニアを 缶得るので、必要な最小回数は である。合成回数を増やすと必要な原料が増えるため、費用は小さくならない。窒素 缶と水素 缶の購入を別々に最適化すればよい。
どちらの原料も、缶価格が低い供給元から順に購入する。高い供給元から購入した缶があり、より安い供給元に未使用の在庫があれば、その缶を安い方から購入するように変更できる。総購入量は変わらず、費用は減る。同じ価格の供給元の順序は費用に影響しない。よって、供給元を価格の昇順に並べ、在庫と残り必要量の小さい方だけ購入すればよい。どちらかの原料が不足する場合は -1 を出力する。
とすると、時間計算量は 、空間計算量は である。購入量は合計 缶で、缶価格は高々 なので、購入可能な場合の答えは最大 である。
Solution written by GPT