#P13091. [FJCPC 2025] 中位数
[FJCPC 2025] 中位数
题目描述
CFJ 拥有一个长度为 的数组 ,且 必定为奇数。
由于 CFJ 十分喜爱中位数,他将进行以下操作:每次选择数组中连续的三个数字,并将它们合并为其中位数,替换这三个数字。具体而言,每次选择任意一个位置 (满足 ),删除 、 和 ,并在该位置插入这三个数字的中位数。
CFJ 将持续进行上述操作,直到数组中仅剩一个数字为止。整个过程共需进行 次合并。他期望这个最终剩余的数字尽可能大。你的任务是帮助 CFJ 确定这个数字的最大可能值。
中位数的定义为:将一组长度为 的数组从小到大排序后,排名第小的数字。
输入格式
本题包含多组测试数据。
第一行,包含一个整数 (),表示测试数据的组数。
对于每组数据:
第一行,包含一个整数 (),且 必定为奇数。
第二行,包含 个整数 ()。
数据保证 。
输出格式
对于每个测试用例,输出 次合并以后剩下数字的最大值。
6
1
1
3
1 2 2
5
1 3 4 5 2
7
1 2 3 5 6 7 4
9
9 9 8 2 4 4 3 5 3
9
4 4 9 2 9 5 8 3 3
1
2
3
5
9
4
提示
对于第四个样例而言,数组 一种可行的方案是:$ [ \ \underline{1 \ 2 \ 3} \ 5 \ 6 \ 7 \ 4 \ ] \rightarrow [ \ \underline{2 \ 5 \ 6} \ 7 \ 4 \ ] \rightarrow [ \ \underline{5 \ 7 \ 4} \ ] \rightarrow [ \ 5 \ ]$。
其中 下划线选择的连续三个数字表示每次操作合并的对象。