思路:二分答案+$dp$ check

$dp_{i,0/1,0/1}$表示前i个数中没有/有保留,删除了偶数/奇数个k个数中大于等于mid(当前中位数)的数量与小于mid的数量的差最大,最后根据剩下来的数的奇偶行判断(其实中间一维可以不用)

Wrong Answer on test 2

其中第268行答案3输出4

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
#define pb(x) push_back(x)
#define size(s) ((int)s.size())
using namespace std;
void inline solve();
signed main(){
	int t=1;
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
}
/*---------------------------------------------------------------------------------------------------------------------*/
const int N=2e5+10,L=1,R=1145141314,inf=1145141314;
int n,k,a[N],dp[N][2][2],l,r,mid,lst;
int inline update(int &res,int val){
	return res=max(res,val);
}
void inline solve(){
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	l=L,r=R;
	while(l+1<r){
		mid=(l+r)/2;
		for(int i=0;i<=n;i++){
			for(int j=0;j<2;j++){
				for(int l=0;l<2;l++){
					dp[i][j][l]=-inf;
				}
			}
		}
		dp[0][0][0]=0;
		for(int i=1;i<=n;i++){
			if(i>=k){
				for(int j=0;j<2;j++){
					for(int l=0;l<2;l++){
						update(dp[i][j][l],dp[i-k][j][l^1]);
					} 
				}
			}
			for(int j=0;j<2;j++){
				for(int l=0;l<2;l++){
					update(dp[i][1][l],dp[i-1][j][l]+(a[i]>=mid?1:-1));
				}
			} 
		}
		int ni=n%2,nj=(n+k)%2,li=2,lj=2;
		if(ni){
			li=1;
		}
		if(nj){
			lj=1;
		}
		if(dp[n][1][1]>=lj || dp[n][1][0]>=li){
			l=mid;
		}else{
			r=mid;
		}
	}
	cout << l << endl;
}