体力が足りなくなった段階で、過去訪れた泉で回復を行っていたとしてシミュレートする。

回復する可能性のある泉の一覧を deque にて管理する。 今、回復量 \(h\) の泉に差し掛かったとき、deque 内に含まれる回復量 \(h\) 以下の泉を使うことはない。(明らかに後に登場する泉を使った方が損しないため)

この観察により、deque 内の泉の回復量は狭義単調減少になっている。

泉によって回復を行う際、体力の上限をオーバーしない限り回復量最大の泉によって回復を行うのが最適である。 このシミュレーションを行うために、deque では、泉の (回復量, この泉で回復する体力の総量) を管理する。

ある泉で回復する体力の総量は、

\[ H - \text{現在の体力} - \text{deque 内のそれ以前の泉で回復する量の和}\]

によって求められる。この値が一回の回復量の倍数でない場合、少し場合分けが必要になるが、全体として \(O(N)\) でシミュレートすることが出来る。

https://atcoder.jp/contests/joi2010ho/submissions/34843412