题意

给定一个长度为 nn 的序列 aa，每次删除其中一个长度为 kk 的子段直到序列长度小于等于 kk，最大化操作完之后序列的中位数。

思路

首先转化一下求解中位数，令当前中位数为 xx，我们构造一个辅助数组 bb，满足 x≤aix\le a_i 时 bi=1b_i=1，否则 bi=−1b_i=-1.

那么 bb 中元素的和一定大于 00.

所以我们可以二分中位数的值，使用 dp 进行 check:

定义 dpidp_i 代表处理完 b1∼bib_1\sim b_i 后 ∑j=1ibi\sum_{j=1}^ib_i 的最大值，则有：

  1. i−1(modk)=0i-1\pmod k=0，dpi=max⁡(dpi−k,bi)dp_i=\max(dp_{i-k},b_i).
  2. otherwise，dpi=max⁡(dpi−1+bi,dpi−k)dp_i=\max(dp_{i-1}+b_i,dp_{i-k}).
code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
mt19937 rnd(1209);
const int N = 5e5 + 10;
int a[N], b[N], n, k, dp[N];
bool check(int x)
{
    for(int i = 1; i <= n; i ++) {dp[i] = -1; if(a[i] >= x) b[i] = 1; else b[i] = -1;}
    dp[1] = b[1];
    for(int i = 2; i <= n; i ++)
    {
        if(i % k == 1 || k == 1) dp[i] = max(dp[i - k], b[i]);
        else
        {
            dp[i] = dp[i - 1] + b[i];
            if(i > k) chmax(dp[i], dp[i - k]);
        }
    }
    return dp[n] > 0;
}
void solve()
{
    int mxa = 0; cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i], chmax(mxa, a[i]);
    int l = 1, r = mxa, res = 0;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) l = mid + 1, res = mid;
        else r = mid - 1;
    } cout << res << "\n";
}
fish main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t --) solve();
    return 0;
}