当前位置: 首页> 游戏> 游戏 > 【题解】CF1993D

【题解】CF1993D

时间:2025/7/9 7:38:04来源:https://blog.csdn.net/qq_40432278/article/details/142252556 浏览次数:0次

目录

  • 翻译
  • 思路
  • 总代码

翻译

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

思路

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

剩余数组的长度 L = ( n − 1 ) m o d k + 1 L=(n-1) \mod k + 1 L=(n1)modk+1
m = ( L + 1 ) / 2 m = (L + 1) / 2 m=(L+1)/2

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

  对于判断环节,我们可以设计一个函数,寻找一种方案,使删除后剩下的数中小于 x x x的最小数量 c n t cnt cnt,那如果 c n t < m cnt < m cnt<m,,则说明存在可行的中位数 y y y,使得 y < x y<x 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;

  接下来完善 c o u n t count count函数。采用 d p dp dp的方式,记 f [ i ] f[i] f[i]表示到第 i i i个数时小于 x x x的数量的最小值(允许不拿 a [ i ] a[i] a[i]),则:

f [ i ] = m i n ( f [ i − 1 ] + ( a [ i ] < x ? 1 : 0 ) , f [ i − k ] ( i f i > = k ) ) f[i]=min(f[i-1]+(a[i]<x?1:0), f[i-k] \quad (if \quad i>=k)) f[i]=min(f[i1]+(a[i]<x?1:0),f[ik](ifi>=k))

  但这样会有一个问题,如果 k ∣ n k | n kn,则这个 d p dp dp会找到一种方案,将所有数都删除,最终返回 0 0 0
  为了解决这个问题,我们标记一下当前方案是否为空即可,即将 f f f数组新增大小为 2 2 2的一维,最后返回 f [ n ] [ 1 ] f[n][1] 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;
} 
关键字:【题解】CF1993D

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: