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[100010];                   
int num[100010];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){            //输入+离散化 
        scanf("%d",&ty);                             
        if(f[ty]) type[i]=f[ty];     //出现过的给原来的编号 
        else type[i]=++tot,f[ty]=tot;   //没出现的更新编号并记录 
    }
    int cnt=1,head=1;num[type[1]]++;    
    for(int i=2;i<=n;i++){
        while(cnt>=k+2){                //当区间内种类数量大于k+2时左端点右移直到个数小于k+2 
            num[type[head]]--;         
            if(num[type[head]]==0)      //当一个种类数量减为零，区间内种类减一 
               cnt--;
            head++;
        }
        if(!num[type[i]]) cnt++;       //更新 
        num[type[i]]++;
        ans=max(ans,num[type[i]]);    //用当前种类更新 
    }
    printf("%d",ans);
    return 0;
}

 

原文链接:https://www.cnblogs.com/tonyshen/p/11766556.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有