【题解】CF1993D

翻译

原题链接

思路

  容易发现，无论如何操作，最后剩下的数量是一定的，记剩下的数组中中位数的位置为$m$（从1开始记），注意不能将数组删空。有：

剩余数组的长度$L=(n-1)\mathrm{mod}k+1$
$m=(L+1)/2$

  显然我们需要一个$O(nlogn)$的算法，根据经验，注意到中位数具有可二分性（显然尽量把小的数删掉中位数肯定大）。所以二分答案中位数是多少，然后$check$这个中位数是否可行。

  对于判断环节，我们可以设计一个函数，寻找一种方案，使删除后剩下的数中小于$x$的最小数量$cnt$，那如果$cnt<m$，，则说明存在可行的中位数$y$，使得$y<x$。根据这些，我们可以写出二分的框架：

int count(int x) {return 剩下的数中小于x的最小数量cnt
} int m = ((n-1) % k + 1 + 1) / 2;
int l = 1, r = 1e9, ans=-1;
while(l<=r) {int mid = l+r>>1;if(count(mid) < m) {   // 最少比mid小的数量比m少 ans = mid;l = mid + 1; } else {r = mid - 1;}
} 
cout<<ans<<endl;

  接下来完善$count$函数。采用$dp$的方式，记$f[i]$表示到第$i$个数时小于$x$的数量的最小值（允许不拿$a[i]$），则：

$f[i]=min(f[i-1]+(a[i]<x?1:0),f[i-k](ifi>=k))$

  但这样会有一个问题，如果$k|n$，则这个$dp$会找到一种方案，将所有数都删除，最终返回$0$。
  为了解决这个问题，我们标记一下当前方案是否为空即可，即将$f$数组新增大小为$2$的一维，最后返回$f[n][1]$。递推式子稍微改一改即可，代码如下：

for(int i=0;i<=n;i++) f[i][0] = f[i][1] = 1e9;
f[0][0] = 0;
for(int i=1;i<=n;i++) {f[i][1] = min(f[i-1][0], f[i-1][1]) + (a[i] < x ? 1 : 0);if(i>=k) {f[i][0] = min(f[i][0], f[i-k][0]);f[i][1] = min(f[i][1], f[i-k][1]);}
} 
return f[n][1];

总代码

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int t, n, k, a[N], f[N][2];
int count(int x) {// 使小于x的数最少// f[i]表示到i，i可以被删除 , 标记是否为空 for(int i=0;i<=n;i++) f[i][0] = f[i][1] = 1e9;f[0][0] = 0;for(int i=1;i<=n;i++) {f[i][1] = min(f[i-1][0], f[i-1][1]) + (a[i] < x ? 1 : 0);if(i>=k) {f[i][0] = min(f[i][0], f[i-k][0]);f[i][1] = min(f[i][1], f[i-k][1]);}} return f[n][1];
} 
int main() {cin>>t;while(t--) {cin>>n>>k;int m = ((n-1) % k + 1 + 1) / 2;  // 第m个数为中位数for(int i=1;i<=n;i++) {cin>>a[i];}int l = 1, r = 1e9, ans=-1;while(l<=r) {int mid = l+r>>1;
//			printf("%d %d\n", mid, count(mid));if(count(mid) < m) {   // 最少比mid小的数量比m少 ans = mid;l = mid + 1; } else {r = mid - 1;}} cout<<ans<<endl;}return 0;
}