SPOJ-EXPEDI, POJ-2431 : Expedition

問題概要

x=0からx=L(<10^6)まで歩く。単位距離歩くのに単位燃料を使用する。最初燃料がP(<10^6)だけある。途中N(<10^4)箇所に補給所があって、距離a[i]のところで燃料をb[i]だけ補給できる。補給回数の最小値を求める問題。

解法

蟻本p.73に載ってる問題。今までに通過した補給所のうちもっとも燃料の多いところを利用することにすれば良い。
ソース略。