题意回顾

我们有 n 种颜色（n 为偶数），每种颜色有 m 张奖券，奖券上印有数字，且同种颜色的奖券数字非递减排列。

游戏进行 k 轮，每轮：

1. 我们从每种颜色中选 1 张 未被使用过的奖券，组成一个大小为 n 的集合。
2. 对手（游戏主持人）看到这个集合的数字 $a_0, a_1, \dots, a_{n-1}$ 后，会选择一个整数 $b$，使得$$S = \sum_{i=0}^{n-1} |a_i - b|$$ 最小。
3. 这个 $S$ 就是本轮我们获得的奖励。
4. 用过的奖券丢弃。

目标：安排奖券的分配方案（即决定每种颜色的哪张奖券在哪一轮使用），使得 k 轮奖励总和最大。

---

对手策略分析

对于给定的一组数 $a_0, a_1, \dots, a_{n-1}$，对手选 $b$ 使 $\sum |a_i - b|$ 最小。

这是一个经典问题：最优的 $b$ 是这组数的中位数（当 $n$ 为偶数时，$b$ 可取两个中间数之间的任意值，最小值相同）。

设 $a$ 已排序为 $a_{(0)} \le a_{(1)} \le \dots \le a_{(n-1)}$，则最小值为：

$$S_{\min} = \sum_{i=0}^{n/2-1} \big(a_{(n-1-i)} - a_{(i)}\big) $$

因为对于排序后的数组，选 $b$ 在中位数区间时，$|a_i - b|$ 的和等于较大一半的和减去较小一半的和（适当配对）。

---

问题转化

因此，对手一定会让本轮奖励等于：

$$S = \sum_{i=0}^{n/2-1} \big(a_{(n-1-i)} - a_{(i)}\big) $$

即：将本轮集合中的 $n$ 个数排序后，较大的一半与较小的一半配对，每对差值求和。

我们要安排所有轮次的集合，使得这个总和最大。

---

最优构造思路

关键观察

要让 $S$ 大，就要让每轮中 较大的一半数尽量大，较小的一半数尽量小，这样差值才大。

因此，全局来看：

• 我们应该把 所有奖券中最大的 $k \cdot n/2$ 张 用作各轮的“较大一半”，
• 把 所有奖券中最小的 $k \cdot n/2$ 张 用作各轮的“较小一半”。

因为 $n$ 是偶数，$k \cdot n/2$ 是整数。

---

分配可行性

每种颜色有 $m$ 张奖券，我们要选出 $k$ 张用于 $k$ 轮（每轮一张）。
所以“较大一半”需要 $k \cdot n/2$ 张奖券，它们来自不同颜色、不同轮次。同样，“较小一半”也需要 $k \cdot n/2$ 张。

我们只需保证：

• 每轮中，每个颜色的奖券只用一次；
• 每轮恰好有 $n/2$ 张来自“较大组”，$n/2$ 张来自“较小组”。

---

构造方法

1. 标记大组与小组
   将全部 $n \cdot m$ 张奖券按数字从小到大排序，取前 $k \cdot n/2$ 张标记为 L（小），后 $k \cdot n/2$ 张标记为 R（大），中间剩余的 $n \cdot m - k \cdot n$ 张标记为 M（中），不使用。

2. 颜色内分配
   对于每种颜色，它有一些 L 票和一些 R 票（可能还有 M 票）。我们要把它的 L 票和 R 票分配到 $k$ 轮中，且每轮该颜色只出一张票。

   问题变成：能否给每种颜色 i 分配它的 L 票到某些轮次，R 票到其余轮次，使得：

   • 总共 $k$ 轮，每轮该颜色恰有一张票；
   • 全局来看，每轮恰有 $n/2$ 张 L 和 $n/2$ 张 R。

   这是一个匹配问题。

3. 配对轮次
   我们可以用贪心法：

   • 对每种颜色，把它最小的 L 票分配给最早的轮次，最大的 R 票分配给最早的轮次，但这样可能冲突。

   • 更标准做法：
     构造一个 $n \times k$ 的表格，每个格子 (颜色, 轮次) 需要填 L 或 R，每行恰好 $k$ 个格子（该颜色的 $k$ 张票），其中 L 的数量 = 该颜色 L 票的数量；每列（每轮）恰好 $n/2$ 个 L 和 $n/2$ 个 R。

     这相当于一个二分图匹配：左侧 $n$ 个颜色节点，每个颜色有 L-count 个 L 需求和 R-count 个 R 需求；右侧 $k$ 个轮次节点，每个轮次需要 $n/2$ 个 L 和 $n/2$ 个 R。
     可以证明，因为总 L 数 = 总 R 数 = $k \cdot n/2$，且每种颜色 L 数 ≤ k，R 数 ≤ k，这种分配总是可行的（类似正则二分图的分解）。

4. 实现分配
   在每轮中，对于该轮分配的 L 票，我们取该颜色最小的可用 L 票；对于 R 票，取该颜色最大的可用 R 票。这样保证每轮内 L 尽量小、R 尽量大，从而差值最大。

---

最大值计算

最大值就是所有配对的差值之和：
我们实际上是把最小的 $k \cdot n/2$ 张票（所有 L）与最大的 $k \cdot n/2$ 张票（所有 R）配对，每对 (R - L) 的和就是答案。

具体计算：

• 把所有奖券数字排序；
• 取最大的 $k \cdot n/2$ 张的和，减去最小的 $k \cdot n/2$ 张的和，即为最大总奖励。

---

总结

这道题的核心步骤：

1. 分析对手策略 → 每轮奖励 = 排序后较大一半和 - 较小一半和。
2. 转化为全局配对 → 全局最小的 $k \cdot n/2$ 张票（L）与最大的 $k \cdot n/2$ 张票（R）配对。
3. 可行性构造 → 在颜色和轮次约束下，将 L 和 R 分配到各轮，保证每轮 L 和 R 各 $n/2$ 张。
4. 计算最大值 → 直接 Sum(R) - Sum(L)。