LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup

题目链接

看了看其他大佬的文章，为什么要控制右端呢

其实就是一个很简单的模拟队列趴。。。

难点就在于根据题意我们可以分析得一段合法区间内，不同种类个数不能超过k+2

哦当然，由于种类数范围过大，要对种类进行离散化，可以使用STL的map

剩下的就是模拟了,详见代码：

#include<bits/stdc++.h>

using namespace std;

map<int,int> f;

int ty,tot,k,n,ans;

int type[];

int num[];

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){            //输入+离散化

        scanf("%d",&ty);

        if(f[ty]) type[i]=f[ty];     //出现过的给原来的编号

        else type[i]=++tot,f[ty]=tot;   //没出现的更新编号并记录

    }

    int cnt=,head=;num[type[]]++;

    for(int i=;i<=n;i++){

        while(cnt>=k+){                //当区间内种类数量大于k+2时左端点右移直到个数小于k+2

            num[type[head]]--;

            if(num[type[head]]==)      //当一个种类数量减为零，区间内种类减一

               cnt--;

            head++;

        }

        if(!num[type[i]]) cnt++;       //更新

        num[type[i]]++;

        ans=max(ans,num[type[i]]);    //用当前种类更新

    }

    printf("%d",ans);

    return ;

}