题解 P3069 【[USACO13JAN]牛的阵容Cow Lineup】

· · 题解

这题为啥是蓝的啊

离散化，然后再。。。。。算了代码解释

#include <bits/stdc++.h>
using namespace std;
int n;
map<int,int> mp;
//离散化
int a[100001];
//存离散化后的数组
int hav[100001];
//存当前区间内，对应数字出现过的次数
int mxl;
//反正就是计数一下
int typ,k;//当前区间里有多少种
int ans;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!mp[a[i]])mp[a[i]]=++mxl;
        //如果当前数字没有出现过，就给他分配一个新的离散化值
        a[i]=mp[a[i]];
    }
    int l=1,r=0;
    //区间
    while(r<=n){
        r++;
        //右移
        if(hav[a[r]]==0)typ++;//如果这个数字第一次出现，种类++
        hav[a[r]]++;
        while(typ==k+2){
        //删除k种，说白了允许当前区间内有k+1种
        如果是k+2种就得删除了
            hav[a[l]]--;
        //左界右移，减少左界位置上值得数量
            if(hav[a[l]]==0)typ--;
        //没了就种类--
            l++;
        }
        ans=max(ans,hav[a[r]]);
        //统计答案
    }
    printf("%d",ans);
    //输出
}

一开始看这道题，蓝的，打算先放放

看了好几篇题解，set,balabala,什么玩意....

按照多篇题解的想法打了一下，也就这样