「DTOI-4」中位数

Luogu
IDLGP8978
Time2000ms
Memory512MB
DifficultyP7
动态规划 DP二分单调队列2023洛谷原创O2优化
给定一个长度为 $n$ 的整数序列 $a$,你可以进行以下操作不超过 $k$ 次: - 选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq n$,并将 $[l, r]$ 中的所有数替换为这个区间的中位数。 你要使得操作后 $a$ 的**最小值最大**。 关于此处中位数的定义:对于一个长度为 $len$ 的序列,其中位数定义为该序列中第 $\lceil \frac{len}{2} \rceil$ 小的数。 ## Input 第一行,两个整数 $n, k$; 第二行,$n$ 个整数 $a_1, a_2, \cdots, a_n$。 ## Output 一行,表示经过不超过 $k$ 次操作后序列最小值的最大值。 [samples] ## Note | $\textbf{Subtask}$ | $n$ | 分值 | | :------: | :------: | :------: | | $1$ | $1 \leq n \leq 10$ | $10 \operatorname{pts}$ | | $2$ | $1 \leq n \leq 100$ | $10 \operatorname{pts}$ | | $3$ | $1 \leq n \leq 10^3$ | $10 \operatorname{pts}$ | | $4$ | $1 \leq n \leq 10^4$ | $20 \operatorname{pts}$ | | $5$ | $1 \leq n \leq 10^5$ | $20 \operatorname{pts}$ | | $6$ | 无特殊限制 | $30 \operatorname{pts}$ | 对于 $100\%$ 的数据,$1 \leq n \leq 4 \times 10^5$,$0 \leq k \leq n$,$0 \leq a_i \leq 10^9$。
Samples
Input #1
10 2
2 8 3 2 5 7 10 4 9 7
Output #1
7
Input #2
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
Output #2
0
Input #3
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
Output #3
1
API Response (JSON)
{
  "problem": {
    "name": "「DTOI-4」中位数",
    "description": {
      "content": "给定一个长度为 $n$ 的整数序列 $a$,你可以进行以下操作不超过 $k$ 次: - 选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq n$,并将 $[l, r]$ 中的所有数替换为这个区间的中位数。 你要使得操作后 $a$ 的**最小值最大**。 关于此处中位数的定义:对于一个长度为 $len$ 的序列,其中位数定义为该序列中第 $\\lceil \\frac",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8978"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的整数序列 $a$,你可以进行以下操作不超过 $k$ 次:\n\n- 选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq n$,并将 $[l, r]$ 中的所有数替换为这个区间的中位数。\n\n你要使得操作后 $a$ 的**最小值最大**。\n\n关于此处中位数的定义:对于一个长度为 $len$ 的序列,其中位数定义为该序列中第 $\\lceil \\frac...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments