P13759 Basketball

Everyone has its own dream.

有 $n$ 个人在野球场上打球，第 $i$ 个人战斗力是 $a_i$，你需要将他们分成 $m$ 组，第 $i$ 组有 $\frac{n}{m}$ 人，保证 $\frac{n}{m}$ 为奇数。 定义本组球员的不团结值为 $x_i$，表示本组所有战斗力值的中位数。 请你给出一种分组方案，使 $\sum_{i = 1}^{m} x_i$ 最小。

第一行两个数，$n$ 和 $m$。 第二行 $n$ 个数，为每个球员的 $a_i$ 战斗力值。

一个数，代表 $\sum_{i = 1}^{m} x_i$ 的最小值。

**『本题采用捆绑测试』** 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$，满足 $m$ 一定是 $n$ 的因数且 $\frac{n}{m}$ 为奇数。 | Subtask | 测试点编号 | 特殊限制 | 分值 | | :-----------: | :----------: | :-----------: | :-----------: | | $\text{Subtask 1}$ | $1 \sim 2$ | $n \le 10$ | $10$ | | $\text{Subtask 2}$ | $3 \sim 5$ | 所有 $a_i$ 相等 | $15$ | | $\text{Subtask 3}$ | $6 \sim 7$ | 对于 $2 \le i \le n$，有 $a_i = a_{i-1} + 1$ | $10$ | | $\text{Subtask 4}$ | $8 \sim 10$ | $m=1$ | $15$ | | $\text{Subtask 5}$ | $11 \sim 13$ | $n \le 2000$ | $15$ | | $\text{Subtask 6}$ | $14 \sim 20$ | 无特殊限制 | $35$ |