题目描述

对于大小为 $m$ 的可重集 $S=\{x_0,x_1,\ldots,x_{m-1}\}$，设其所有元素 从大到小 排序后的结果为 $y_0\ge y_1\ge\cdots\ge y_{m-1}$。定义其 中位数 $\operatorname{Median}(S)$ 为其中第 $\left\lceil\frac{m}{2}\right\rceil$ 大的数，即 $\operatorname{Median}(S)=y_{\left\lceil\frac{m}{2}\right\rceil-1}$。注意：本题中的中位数定义与常规定义可能有所不同。

给定长度为 $n$ 的序列 $[a_0,a_1,\ldots,a_{n-1}]$，以及一个正整数 $k$（$k\le n$）。定义一个 划分 如下：选择一个长度为 $k-1$ 的递增下标序列 $0<b_1<\cdots<b_{k-1}<n$，即可将原序列划分为 $k$ 个段，对应的下标区间依次为 $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$。

对于一个划分，定义该划分的 平衡度 如下：对于划分出的每个段，计算其中所有元素形成的可重集的中位数，则这 $k$ 个中位数形成的可重集的中位数即为该划分的 平衡度。形式化地，对于划分 $b_1,\ldots,b_{k-1}$，记 $b_0=0$，$b_k=n$，设第 $i$（$0\le i<k$）个段中所有元素形成的可重集的中位数为 $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$，则该划分的平衡度为 $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$。

请求出所有划分中平衡度的最大值。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 median.h，即在程序开头加入以下代码：

#include "median.h"

选手需要在提交的程序源文件 median.cpp 中实现以下两个函数：

void init(int c, int t);

• $c,t$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被评测程序调用恰好一次。

int median(int n, int k, std::vector<int> a);

• $n,k,a$ 分别表示序列长度、划分的段数与给定的序列。
• 该函数需要返回平衡度的最大值。
• 对于每个测试点，该函数会被评测程序调用恰好 $t$ 次。

本试题目录下的 template_median.cpp 是提供的示例代码，选手可参考并实现自己的代码。

输入格式

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行文件：

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

对于编译得到的可执行文件 median：

• 可执行文件将从标准输入读入以下格式的数据：
  • 第一行包含两个非负整数 $c,t$。
  • 接下来依次为每组测试数据。对于每组测试数据：
    • 第一行包含两个正整数 $n,k$。
    • 第二行包含 $n$ 个正整数 $a_0,a_1,\ldots,a_{n-1}$。
• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行一个正整数，表示平衡度的最大值。

输出格式

无

输入输出样例 #1

输入 #1

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

输出 #1

9
8

说明/提示

【样例 $1$ 解释】

对于第一组测试数据，一种平衡度最大的划分为 $b_1=3$，$b_2=5$，$b_3=7$，其将原序列划分为 $4$ 个段 $[6,5,1]$、$[9,2]$、$[3,10]$、$[7,4,8]$，段中所有元素的中位数分别为 $5,9,10,7$，因此该划分的平衡度为 $\operatorname{Median}(\{5,9,10,7\})=9$。

对于第二组测试数据，一种平衡度最大的划分为 $b_1=2$，$b_2=4$，$b_3=6$，$b_4=8$，其将原序列划分为 $5$ 个段 $[5,7]$、$[3,10]$、$[8,2]$、$[9,1]$、$[6,4]$，段中所有元素的中位数分别为 $7,10,8,9,6$，因此该划分的平衡度为 $\operatorname{Median}(\{7,10,8,9,6\})=8$。

【样例 $2$】

见选手目录下的 median/median2.in 与 median/median2.ans。

该样例满足测试点 $6$ 的约束条件。

【样例 $3$】

见选手目录下的 median/median3.in 与 median/median3.ans。

该样例满足测试点 $9$ 的约束条件。

【样例 $4$】

见选手目录下的 median/median4.in 与 median/median4.ans。

该样例满足测试点 $14$ 的约束条件。

【样例 $5$】

见选手目录下的 median/median5.in 与 median/median5.ans。

该样例满足测试点 $18\sim20$ 的约束条件。

【数据范围】

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有：

• $1\le t\le20$；
• $5\le n\le10^6$，$2\le k\le n$，$N\le10^6$；
• 对于所有 $0\le i<n$，均有 $1\le a_i\le n$。

::cute-table{tuack}

特殊性质 $A$：对于所有 $0\le i<n$，均有 $a_i\le2$。

附件下载

median.zip 6.60MB