由于某些原因本题仅支持 C++, C++11 语言的提交。
Ringo 正在参加在新加坡举办的一个嘉年华活动。他的口袋里装有一些奖券,这些奖券可以在嘉年华的游戏展位使用。假设共有 $n$ 种颜色的奖券,每张奖券涂上了其中的一种颜色并且印上了一个非负整数。不同奖券上的数字可能相同。依据嘉年华活动的规则要求,$n$ 保证是偶数。
Ringo 每种颜色的奖券有 $m$ 张,也就是说他共有 $n\cdot m$ 张奖券。其中,第 $i$ 种颜色对应的第 $j$ 张奖券上印的数字为 $x_{i,j}$($0\le i\le n-1$ 且 $0\le j\le m - 1$)。
一次奖券游戏要进行 $k$ 轮,轮次的序号从 $0$ 到 $k-1$。每一轮按照下面的方式进行:
首先,Ringo 从每种颜色的奖券中各选出一张奖券,形成一个 $n$ 张奖券的集合。
随后,游戏负责人记录下这个集合中奖券上的数字 $a_0, a_1, \dots, a_{n-1}$。不需要考虑这 $n$ 个整数的顺序。
接下来,游戏负责人从一个幸运抽奖箱中抽取一张特殊卡片,上面印有整数 $b$。
对于上述集合中每一个奖券上的数字 $a_i(0\le i \le n-1)$,游戏负责人会计算 $a_i$ 和 $b$ 的差的绝对值。让 $S$ 代表这 $n$ 个差的绝对值之和。
所得到的数字 $S$ 就是 Ringo 本轮能够获得的奖励数额。
一轮游戏结束后,本轮集合中的奖券全部被丢弃,不会在未来的轮次所使用。
当 $k$ 轮游戏结束后,Ringo 会丢弃口袋中的所有奖券。
通过仔细观察,Ringo 发现这个奖券游戏被操控了!实际上,幸运抽奖箱里面内置了一台打印机。在每一轮,游戏负责人首先找到一个能够最小化当前轮次游戏奖励的整数 $b$,然后将该数字打印在他所抽取的特殊卡片上。
知道了这些信息之后,Ringo 想要设计每轮游戏中的奖券分配方案,使得 $k$ 轮游戏中获得的总体奖励数额之和最大。
实现细节
你必须引用 tickets.h
头文件。
你需要实现下面这个函数:
long long find_maximum(int k, std::vector<std::vector<int>> x)
$k$:游戏的轮数。
$x$:一个 $n\times m$ 的数组,记录了奖券上的数字。每种颜色的奖券按照上面的数字非递减顺序排序。
这个函数只会被调用一次。
这个函数应该只调用一次函数
allocate_tickets
(参见下面的内容),它描述了 $k$ 轮游戏中的奖券分配方案,每一轮对应一个奖券集合。奖券的分配方案应该使得所获奖励数额之和达到最大。这个函数需要返回能够获得的最大的奖励数额之和。
函数 allocate_tickets
按照如下的方式进行定义:
void allocate_tickets(std::vector<std::vector<int>> s)
$s$:一个 $n\times m$ 的数组。如果第 $i$ 种颜色的第 $j$ 张奖券如果被分配到了第 $r$ 轮游戏,那么 $s_{i,j}$ 的值应该为 $r$;如果未被使用,应该为 $-1$。
对于 $0\le i\le n-1$,在 $s_{i,0}, s_{i,1}, \dots, s_{i,m-1}$ 中,每个值 $0, 1, \dots, k - 1$ 必须只出现一次,而其他元素应该为 $-1$。
如果存在多种奖券分配方案能够达到最优的奖励数值,可以给出其中任何一种最优方案。
输入格式
评测程序示例按照下面的格式读入数据:
- 第 $1$ 行:$n\ m\ k$
- 第 $2 + i$ 行($0\le i\le n-1$):$x_{i, 0}\ x_{i,1}\ \dots\ x_{i,m-1}$
输出格式
评测程序示例按照下面的格式打印你的答案:
- 第 $1$ 行:
find_maximum
的返回值 - 第 $2 + i$ 行($0\le i\le n-1$):$s_{i, 0}\ s_{i,1}\ \dots\ s_{i,m-1}$
样例一
input
2 3 2 0 2 5 1 1 3
output
7 0 -1 1 -1 1 0
explanation
考虑下面的函数调用:
find_maximum(2, [[0, 2, 5],[1, 1, 3]])
这意味着: - 游戏共进行 $k=2$ 轮; - 第 $0$ 种颜色奖券上的整数数字分别是 $0, 2$ 和 $5$; - 第 $1$ 种颜色奖券上的整数数字分别是 $1, 1$ 和 $3$;
一种能够获得最优奖励数值的分配方案是:
在第 $0$ 轮,Ringo 选择第 $0$ 种颜色的第 $0$ 张奖券(印有整数 $0$)和第 $1$ 种颜色的第 $2$ 张奖券(印有整数$3$)。本轮获得的最小奖励数额是 $3$。例如,游戏负责人可以选择 $b=1$:$|1-0| + |1-3| = 1+2 = 3$。
在第 $1$ 轮,Ringo 选择第 $0$ 种颜色的第 $2$ 张奖券(印有整数 $5$)和第 $1$ 种颜色的第 $1$ 张奖券(印有整数 $1$)。本轮能够获得的最小奖励是 $4$。例如,游戏负责人可以选择 $b=3$:$|3-1|+|3-5|=2+2=4$。
因此,本次游戏两轮的奖励之和为 $3+4=7$。
为了给出这个分配方案,函数 find_maximum
应该按照如下方式调用 allocate_tickets
:
allocate_tickets([[0, -1, 1], [-1, 1, 0]])
最终,函数 find_maximum
应该返回数字 $7$。
样例二
input
4 2 1 5 9 1 4 3 6 2 7
output
12 -1 0 0 -1 0 -1 -1 0
eplanation
考虑下面的函数调用:
find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])
这意味着:
- 游戏只进行一轮;
- 第 $0$ 种颜色奖券上的数字分别是 $5$ 和 $9$;
- 第 $1$ 种颜色奖券上的数字分别是 $1$ 和 $4$;
- 第 $2$ 种颜色奖券上的数字分别是 $3$ 和 $6$;
- 第 $3$ 种颜色奖券上的数字分别是 $2$ 和 $7$;
一种能够获得最优奖励的分配方案是:
- 在第 $0$ 轮,Ringo 选择第 $0$ 种颜色的第 $1$ 张奖券(印有整数 $9$) ,第 $1$ 种颜色的第 $0$ 张奖券(印有整数 $1$),第 $2$ 种颜色的第 $0$ 张奖券(印有整数 $3$),第 $3$ 种颜色的第 $1$ 张奖券(印有整数 $7$)。本轮能够获得的最小奖励是 $12$。例如,游戏负责人可以选择 $b=3$:
$$ |3-9| + |3-1| + |3-3| + |3-7| = 6 + 2 + 0 + 4 = 12 $$
为了给出这个分配方案,函数 find_maximum
应该按照如下方式调用 allocate_tickets
:
allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])
最终,函数 find_maximum
应该返回数字 $12$。
限制与约定
对于 $100\%$ 的数据,保证:
- $2\le n\le 1500$ 且 $n$ 为偶数
- $1\le k\le m\le 1500$
- $0\le x_{i,j}\le 10^9$(对于所有的 $0\le i\le n-1$ 且 $0\le j\le m-1$)
- $x_{i,j-1}\le x_{i,j}$(对于所有的 $0\le i\le n-1$ 且 $1\le j\le m-1$)
子任务 | 附加限制 | 分值 |
---|---|---|
$1$ | $m=1$ | $11$ |
$2$ | $k=1$ | $16$ |
$3$ | $0\le x_{i,j}\le 1$(对于所有的 $0\le i\le n-1$ 且 $0\le j\le m-1$) | $14$ |
$4$ | $k=m$ | $14 $ |
$5$ | $n,m\le 80$ | $12$ |
$6$ | $n,m\le 300$ | $23$ |
$7$ | 没有其他限制 | $10$ |
时间限制:$2 \texttt{s}$
空间限制:$1024 \texttt{MB}$