ツバサの備忘録

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

ABC117 C - Streamline

問題
提出コード

解法

最初は端にコマを置いていけばいい、と思ったのですが全然違いました。
ある座標の周辺に、目標の座標が密集していると、この通りにはいきません(そもそもサンプル1でこの解法は落ちます)。
そこで、どうするかというと、目標の座標の差を上手く利用します。
N個のコマそれぞれに、区間をうまく割り当てて、その範囲にあるX をカバーしてもらうことを考えます。
すると、それぞれのコマの区間同士の差ができるだけ広くなればよいわけです。
コマi[l_{i},r_{i}]をカバー、j[l_{j},r_{j}]をカバーするとし、iの方が値が小さいとします。すると、
[r_{i}+1,l_{j}-1]はどちらのコマもカバーしない場所になります。ここに、目標のXが入らないようにうまく区間を作成したとき、求める値は結局次のようになります。
Xを降順でソートし、一番大きい値から一番小さい値を引く(Dとします)。その後、Xの隣り合った座標の差をM-1個すべて求め、それをまた降順にソートする。その後、大きい方からN-1個取り出し、Dから引く。
で、最終的に出てきた値が求める答えになります。
N個コマがあるので、その間にある区間N-1個になります。その区間を、大きい方から順番に選んでいけば、目標の値をどんどん小さいものにできます。
N \geqq Mのときは、問答無用で答えが0になることに注意してください。REを吐く可能性が出てきます。