yukicoder No.1015 おつりは要らないです解説

1円玉、5円玉、10円玉で考える。

支払う金額がそれぞれ$ A_i+1円以上であればよい。

10円の支払い方法は

(a)10円玉1枚

(b)5円玉2枚

(d)1円玉10枚

の4通りある。

同じ金額を支払うのであれば、残り硬貨枚数の多い方が嬉しい。したがって(a),(b),(c),(d)の順で消費するのが最適(★)。

$ A_i+1≧10ならば必ず支払った硬貨で1組は丁度10円の組ができる。よって★に従えば残り9円以下までは貪欲に減らせる。

いま$ A_i+1≦9となっている。10円玉はどのiで用いても支払い完了になるので$ A_iの大きい方から順に割り当てる。

残りは1円玉と5円玉となった。

5円の支払い方法は

(e)5円玉1枚

(f)1円玉5枚

の2通りある。

同じ金額を支払うのであれば、残り硬貨枚数の多い方が嬉しい。したがって(e),(f)の順で消費するのが最適。★と同様にして残り4円まで貪欲に減らせる。5円玉はどのiで用いても支払い完了になるのでA_iの大きい方から順に割り当てる。残りは1円玉なので順番に割り当てればよい。