luogu#P8978. 「DTOI-4」中位数

「DTOI-4」中位数

题目描述

给定一个长度为 nn 的整数序列 aa,你可以进行以下操作不超过 kk 次:

  • 选择一个区间 [l,r][l, r] 满足 1lrn1 \leq l \leq r \leq n,并将 [l,r][l, r] 中的所有数替换为这个区间的中位数。

你要使得操作后 aa最小值最大

关于此处中位数的定义:对于一个长度为 lenlen 的序列,其中位数定义为该序列中第 len2\lceil \frac{len}{2} \rceil 小的数。

输入格式

第一行,两个整数 n,kn, k

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

输出格式

一行,表示经过不超过 kk 次操作后序列最小值的最大值。

10 2
2 8 3 2 5 7 10 4 9 7
7
30 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
0
31 3
1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1
1

提示

Subtask\textbf{Subtask} nn 分值
11 1n101 \leq n \leq 10 10pts10 \operatorname{pts}
22 1n1001 \leq n \leq 100
33 1n1031 \leq n \leq 10^3
44 1n1041 \leq n \leq 10^4 20pts20 \operatorname{pts}
55 1n1051 \leq n \leq 10^5
66 无特殊限制 30pts30 \operatorname{pts}

对于 100%100\% 的数据,1n4×1051 \leq n \leq 4 \times 10^50kn0 \leq k \leq n0ai1090 \leq a_i \leq 10^9