CF1468H K and Medians 题解
每次删数都会删恰好 \(k-1\) 个，所以删的数总个数必须是 \(k-1\) 的倍数。考虑最终状态，如果所有数左边不足 \(\frac{k-1}{2}\) 个删掉的数或右边不足 \(\frac{k-1}{2}\) 个删掉的数，那么最后一步是无法实现的。否则，实现了最后一步之后，就可以很轻松的实现前面那些步（可以把最后一步删掉的那些数作为中位数继续删）。所以只需要判断上面两种限制即可。
点击查看代码
#include
#include
const int N=2e5+13;
int a[N];
int main(){
int T;scanf("%d",&T);while(T--){
int n,k,m,x;scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;++i) scanf("%d",&a[i]);
if((n-m)%(k-1)){puts("NO");continue;}
bool ok=0;
for(int i=1;i<=m;++i){
int pre=a[i]-i,suf=(n-a[i]+1)-(m-i+1);
if(pre>=(k-1)/2&&suf>=(k-1)/2){ok=1;break;}
}
puts(ok?"YES":"NO");
}
return 0;
}
//H