ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC052 D - Walk and Teleport

問題
提出コード

解法

この手の問題は、まずテレポートをする回数を固定しましょう。
ということで、テレポートする回数をk回とします。このとき、徒歩で移動する区間の個数はN-1-k個になります。
徒歩で移動する区間はどこになるかというと、区間の距離が小さい方から選んだN-1-k個になります。
前から順番に、徒歩でいくと決めた区間なら徒歩で1つ先の場所へ、徒歩でいかないと決めた区間は1つ先の場所へテレポートで移動すればよいです。
ということで、これを繰り返していると、結局は
 A×(X_i - X_{i-1} )\leqq Bならば徒歩で、そうでなければテレポートで移動すればよいことになります。
ということで、全ての区間について、距離にAをかけたものと、Bを比較して、小さいものを足していけば答えとなります。