AT_tkppc2016_f NPCの家 (NPC's House)

[problemUrl]: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_f NPCの動きを確認したjoisinoお姉ちゃんは、今度はNPCの家の配置を任された。 左右に無限に伸びる直線上に、$ N $人のNPCが立っている。 そして、その直線上に$ M $軒のNPCの家を設置する。 そして、各NPCは自分に最も近い家へと戻ることになる。 このゲームでは、NPCの家は、リアリティーを追求するために、各NPCが家に戻るまでの距離の合計を最小化する位置に家を設置しなければならない。 この作業を効率よくすすめるため、joisinoお姉ちゃんは各NPCが家に戻るまでの距離の合計の最小値を求めるプログラムを書くことにした。

N/A

N/A

### 配点 この問題には部分点が設定されている。 - データセット1は、$ N\ ≦\ 300,\ M\ ≦\ 300 $を満たし、正解すると10点を得られる。 - データセット2では追加の制約はなく、正解すると110点を得られる。 ### 出力 各NPCが家に戻るまでの距離の合計の最小値を出力せよ。 - - - - - - ### 入力例1 ``` 5 2 -3 -1 0 2 5 ``` ### 出力例1 ``` 6 ``` - 例えば、$ -1,\ 2 $の位置に家をおいた時、NPC$ 1,\ 2,\ 3 $は$ -1 $の位置の家に戻り、NPC$ 4,\ 5 $は$ 2 $の位置の家へ戻るので、各NPCが家に戻るまでの距離の合計は$ 2\ +\ 0\ +\ 1\ +\ 0\ +\ 3\ =\ 6 $となる。 - そして、これよりも各NPCが家に戻るまでの距離の合計を小さくする配置はないため、$ 6 $が答えとなる。 - - - - - - ### 入力例2 ``` 10 3 -3 12 -92 -45 -15 27 14 94 -39 75 ``` ### 出力例2 ``` 131 ```