一道贪心题。
根据题意,我们需要在原序列中找出一条从 \(1\) 到 \(n\) 的路径,这条路径能被分成几个长度为 \(k\) 且颜色相等的连续段。我们可以将这个问题简单化,那么这个问题就能被转化为从 \(1\) 开始向后找一个颜色连续段,从 \(n\) 开始向前找一个颜色相同的连续段,只要这两个连续段不相交即可,代码实现时需要注意特判。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int t;
int n,k;
int a[N];
int main(){
t=read();
while(t--){
n=read();
k=read();
bool fl=0;
for(int i=1;i<=n;i++){
a[i]=read();
if(a[i]!=a[i-1]&&i!=1) fl=1;
}
if(!fl&&n==k){
printf("YES\n");
continue;
}
int last=a[n];
int fir;
int now=0;
for(int i=n;i;i--){
if(a[i]==last) now++;
if(now==k){
fir=i;
break;
}
}
if(now!=k){
printf("NO\n");
continue;
}
int st=a[1];
int ls;
now=0;
for(int i=1;i<=n;i++){
if(a[i]==st) now++;
if(now==k){
ls=i;
break;
}
}
if(st==last){
now=0;
for(int i=2;i<n;i++){
if(a[i]==st) now++;
}
if(now+2>=k) printf("YES\n");
else printf("NO\n");
continue;
}
if(now!=k){
printf("NO\n");
continue;
}
if(ls<=fir){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}