A16471. Table with Numbers
编程题
普及-
知识点
题目描述
Peter 画了一个大小为 $h \times l$ 的表格，并用零填充该表格。我们将按从上到下编号其行数为 $1$ 到 $h$，从左到右编号其列数为 $1$ 到 $l$。Ned 想出了一个数列 $a_1, a_2, \ldots, a_n$，并想用它来修改这个表格。
Ned 可以从他的数组中选择 $2k \leq n$ 个数，并把它们分成 $k$ 对。然后，对于每一对 $x, y$，他将取表格中第 $x$ 行第 $y$ 列的单元格，并在该单元格中的数字加 $1$。如果这个单元格不存在，则这对数对表格没有任何影响。
Peter 支持 Ned 的这个想法，并要求他最大化表格中所有数字的总和。请帮助 Ned 计算他能够获得的表格数字总和的最大值。
Ned 可以从他的数组中选择 $2k \leq n$ 个数，并把它们分成 $k$ 对。然后，对于每一对 $x, y$，他将取表格中第 $x$ 行第 $y$ 列的单元格，并在该单元格中的数字加 $1$。如果这个单元格不存在，则这对数对表格没有任何影响。
Peter 支持 Ned 的这个想法，并要求他最大化表格中所有数字的总和。请帮助 Ned 计算他能够获得的表格数字总和的最大值。
输入格式
每个测试包含多组用例。第一行包含测试用例数 $t$（$1 \leq t \leq 500$）。每个测试用例的描述如下：
每个测试用例的第一行包含三个整数 $n$、$h$ 和 $l$（$2 \leq n \leq 100$，$1 \leq h, l \leq 1000$）——数组的大小、表格的高度和宽度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 1000$）——数据本身。
每个测试用例的第一行包含三个整数 $n$、$h$ 和 $l$（$2 \leq n \leq 100$，$1 \leq h, l \leq 1000$）——数组的大小、表格的高度和宽度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 1000$）——数据本身。
输出格式
对于每个测试用例，输出表格中所有数字和的最大可能值。
输入输出样例
输入 #1
7 2 1 1 1 1 5 2 2 1 2 2 3 2 8 4 2 7 2 2 2 3 4 4 2 7 3 6 10 4 1 3 5 4 6 2 4 4 5 5 7 6 3 10 4 1 3 5 4 6 4 1 1 1 1 1 1
输出 #1
1 2 3 2 0 2 2
说明/提示
在第一个测试用例中，Ned 可以取数对 $(1, 1)$，将第 $1$ 行第 $1$ 列的数加 $1$。
在第二个测试用例中，Ned 可以取 $1, 2, 2, 2$ 这四个数字，把它们两两配对为 $(1, 2), (2, 2)$。这样，表格中将有两个单元格为 $1$，因此总和为 $2$。可以证明无法取得更大的和。
在第五个测试用例中，Ned 唯一能够取得的数对是 $(5, 5)$。但表格中不存在第 $5$ 行第 $5$ 列，所以表格总和不能超过 $0$。
在第七个测试用例中，Ned 可以这样配对数字：$(1, 1), (1, 1)$。这样，表格中唯一的单元格会包含 $2$，因此和也是 $2$。可以证明无法获得更大的和。
在第二个测试用例中，Ned 可以取 $1, 2, 2, 2$ 这四个数字，把它们两两配对为 $(1, 2), (2, 2)$。这样，表格中将有两个单元格为 $1$，因此总和为 $2$。可以证明无法取得更大的和。
在第五个测试用例中，Ned 唯一能够取得的数对是 $(5, 5)$。但表格中不存在第 $5$ 行第 $5$ 列，所以表格总和不能超过 $0$。
在第七个测试用例中，Ned 可以这样配对数字：$(1, 1), (1, 1)$。这样，表格中唯一的单元格会包含 $2$，因此和也是 $2$。可以证明无法获得更大的和。