seuOJ480 - 至少一半要相等

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：Div.1, 2024

题目描述

"There are as many even numbers as natural numbers."

现在有一个长度为 $n$($n$为偶数) 的序列，该序列中数字互不相同，你需要选择一个正整数 $k$，然后对序列中任意一个数字 $a_i$ 执行任意次如下操作：

在一定次数的该操作后，你需要使序列中至少一半的数字相等，请问 $k$ 的最大值是多少，如果 $k$ 可以无限大，则输出 $0$。

输入格式

第一行，一个整数 $t(1\le t \le 100)$。
对于每组数据：
第一行，一个整数 $n(2\le n \le 5000)$，$n$ 是一个偶数，代表序列长度。
接下来一行，一个长度为 $n$ 的序列 $a$，该序列中数字互不相同，其中的每个数字 $1\le a_i \le 10^6$。

保证在同一测试点内的 $\sum n \le 5000$。

输出格式

对于每组数据，输出一行代表可行的 $k$ 的最大值，如果 $k$ 可以无限大，则输出 $0$。

样例

输入样例

3
6
1 2 3 4 5 6
2
1 10 
8
1 5 4 9 8 13 12 11 

输出样例

2
0
4

提示
在样例的第 $3$ 组数据中，我们按照以下下标的顺序操作序列中的数组，使得它们分别减去 $4$。
选择 $i=2$，序列变为 $[1,1,4,9,8,13,12,11]$。
选择 $i=4$，序列变为 $[1,1,4,5,8,13,12,11]$。
继续选择 $i=4$，$i=6$，$i=6$，$i=6$，最终序列变为 $[1,1,4,1,8,1,12,11]$，此时序列中存在 $4$ 个 $1$，满足序列中至少一半的数字相等的要求。可以证明的是，如果选择大于 $4$ 的其它数字，不可能在有限次操作内使得序列中至少一半的数字相等。