当前位置：首页 > news >正文

【题解】CF1993D

news 来源：原创 2024/9/21 22:53:23

翻译

原题链接
在这里插入图片描述

思路

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

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

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

对于判断环节，我们可以设计一个函数，寻找一种方案，使删除后剩下的数中小于 $x$ 的最小数量 $c n t$ ，那如果 $c n t < 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;

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

$\quad (if \quad i>=k))$

但这样会有一个问题，如果 $k ∣ n$ ，则这个 $d p$ 会找到一种方案，将所有数都删除，最终返回 $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;
}