【CodeForces 616D】Longest k-Good Segment

n个数里,找到最长的一个连续序列使里面最多k个不同的数。

分析

尺取法,每次R++,如果第R个数未出现过,那么不同的数+1,然后这个数的出现次数+1,如果不同的数大于k了,那就要去掉第L个数,直到不同的数为k,然后更新答案。

代码

#include<cstdio>
#define ll long long
#define N 500005 int n,k;
int a[],num[];
int l,r;
int s,ansl,ansr; int main()
{
scanf("%d%d",&n,&k);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
ansl=;
ansr=k;
l=;
r=;
while(r<n)
{
r++;
if(num[a[r]]==)s++;
num[a[r]]++;
while(s>k)
{
num[a[l]]--;
if(num[a[l]]==)s--;
l++;
}
if(r-l>ansr-ansl)
{
ansr=r;
ansl=l;
}
}
printf("%d %d",ansl,ansr);
return ;
}

  

上一篇:MongoDB(一):关系型数据库和非关系型数据库


下一篇:iPhone白苹果怎么办?白苹果各种解决办法方法