CF1993D-二分+dp处理中位数

大致题意

给定两个正整数 n 和 k 以及另一个由 n 个整数组成的数组 a 。

在一次操作中，可以选择 a 的任意一个大小为 k 的子数组，然后将其从数组中删除，而不改变其他元素的顺序。更正式地说，假设$ (l,r) $是对子数组 \(a_l,a_{l+1},…,a_r\) 的操作，使得 \(r−l+1=k\) ，那么执行此操作意味着将 a 替换为 $[a_1,…,a_{l−1},a_{r+1},…,a_n ] $。

例如，如果 $a=[1,2,3,4,5] $，我们对这个数组执行 \((3,5)\) 操作，它就会变成 \(a=[1,2]\) 。此外，操作 \((2,4)\) 的结果是 \(a=[1,5]\) ，操作 \((1,3)\) 的结果是 \(a=[4,5]\) 。

当 a 的长度大于 k (即 $|a| > k $)时，你必须重复操作。处理后，数组 a 中所有剩余元素的最大可能中值是多少？

• 对长度为 n 的数组中的元素按非递减顺序排序后，中位数是索引为$ ⌊(n+1)/2⌋$ 的元素。例如 $median([2,1,5,4,3])=3 \(、\) median([5])=5 和 median([6,8,2,4])=4 $。

解题思路

我们可以通过二分答案+dp的形式来解决这个问题

通过二分中位数p，每次通过dp检查是否能够满足当前的中位数，在处理中位数一类的题目中非常常见

我们重点讨论dp的过程：

我们在处理中位数类型的dp时常见的操作是将数值\(a_i\)根据其与中位数\(mid\)的关系，分别处理为\(+1(a_i>mid)或者-1（a_i<mid）\),对其求前缀和，若\(f[n]>0\)表示当前中位数可以实现

再结合本题，本题考虑删除长度为k的子序列，通过观察我们可以发现我们需要将整个序列按照长度k划分，例如序列\(a=[1,2,3,4,5,6]\),如果k==2我们可以将其划分为\([1,2][3,4][5,6]\),每一段的第一个元素（\((i-1) \% k == 0\)）我们要特殊考虑

• 若\((i-1)\%k==0\),那么考虑两种情况：
  • 作为一个最终结果的开始 \(f[i] = val\)
  • 前k个被删除，作为上上个段的一部分\(f[i] = f[i-k]\)
• 否则也考虑两种情况：
  • 继续作为上一个段的一部分：\(f[i] = f[i-1]+val\)
  • 前k个被删除，作为上上个段的一部分：\(f[i] = f[i-k]\)

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
void solve()
{
	int n,k;
	cin>>n>>k;
	vector<int> a(n+1);
	for(int i = 1;i <= n;++i) cin>>a[i];
	auto check = [&](int mid)
	{
		vector<int> f(n+1,-1e9);
		f[0] = 0;
		for(int i = 1;i<= n;++i)
		{
			int val = (a[i]>=mid?1:-1);
			if((i-1)%k==0)
			{
				if(i-k>=0)
					f[i] = max(f[i-k],val);
				else
					f[i] = val;
			} 
			else{
				if(i-k>=0) f[i] = max(f[i-1]+val,f[i-k]);
				else f[i] = f[i-1]+val;
			}
		}
		return f[n]>0;
	};
	int l = 1,r = 1e9+7;
	while(l<r)
	{
		int mid = (l+r+1)/2;
		if(check(mid)) l=mid;
		else r = mid-1;
	} 
	int ans = r;
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin>>tt;
	while(tt--)solve();
	return 0;
}