ABC117 C - Streamline
問題概要
数直線上にN個の駒を置く。操作1回につき1個の駒をその駒の座標+1か-1の場所に移動できる。訪れたいマス目の一覧が与えられるので何回の操作で全てのマス目を訪れられるか解答する。
解法
まず、明らかにN>=Mの場合は訪れたいマス全てに最初から駒を置けるので0回の操作で完了する。
次に、マス目はソートしても一般性を失わないため、ソートする。すると、駒はN個あるので任意の2マスの間の距離は駒を1個多く使うことにより差を埋めることができることが分かる(写真は入出力例1を表しています。参考にどうぞ。)。
よってソートした後に2マス間の絶対値距離を持ってあげて、それをソートし(写真でいえば1,2,2,8のようになる)、N-1個分だけ差減らしてあげると画像の例では1+2+2=5となる。これらを素直に実装してあげて、AC。
