题意:
给出一个长度为 (n) 的数组 (a),以及数字 (k),在一次操作中可以选择一个区间 ([l,r]),把这个区间里所有的数字变成其中位数,数组 (a) 的中位数是排好序之后的 (a[frac{n+1}{2}])。问是否可以通过有限次操作,把整个区间变成 (k)。
传送门
分析:
主要还是思考问题的角度,从部分推整体。
要达到目的,那么 (k) 必然要出现在数组 (a) 中。
把数组中的所有的数分成三类:(0) 表示小于 (k) 的数,(1) 表示等于 (k) 的数,(2) 表示大于 (k) 的数。
当 (n=1) 时,直接判断。
当 (n>1) 时,
当有超过两个 (1) 连续时,必然可以通过以两个 (1) 为基础向左右一个一个的拓展来实现目的。
当只有单独的1时,
如果出现:(12/21) 的情况,可以转化为 (11),满足;
当出现: (10/01) 的情况,
取解于第三个数的情况,如果是 (101/102) 仍可以;但如果出现 (100) 则不满足情况。
因此,只要满足出现一次:两个均大于等于1的数之间的间距小于等于 (2),即可。
题解证明
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
int t,n,k;
scanf("%d",&t);
while(t--)
{
bool f=0,ff=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==k) ff=1;
}
if(n==1&&ff) f=1;
if(ff&&!f)
{
int last=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=k)
{
if(i-last<=2&&last>0)
{
f=1;
break;
}
last=i;
}
}
}
if(f) printf("yes
");
else printf("no
");
}
return 0;
}