逛画展

题目 逛画展

思路分析

又是一个种类与个数的问题

要维护一个区间 里面包含所有名师的画 也就是种类要都有

用一个队列维护 cnt记录每种画的数量 ans记录种数

首先得让队列里包含所有种数的画

才能考虑优化区间 这个优化只能在队头 即那种画在后面有出现过 我的l就可以往右压缩

最后的答案只有后找到的l，r长度小于之前的才更新（等于不行）

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=1e6+10,M=2010;

int q[N],hh=1,tt=0;

int cnt[M],ans;

PII res;

int n,m;

int main()

{

    //不加1162ms 超1s限制 加了后305ms

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n>>m;

    res.first=0,res.second=2e6;

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

        int x;

        cin>>x;

        if(!cnt[x])

            ans++;

        cnt[x]++;

        while(cnt[q[hh]]>=2)

            cnt[q[hh]]--,hh++;

        q[++tt]=x;

        if(ans==m && tt-hh<res.second-res.first)

            res={hh,tt};

    }

    cout<<res.first<<" "<<res.second;

    return 0;

}

同类题型

视频讲解

⬅️ 蚯蚓 🏠 00-刷题理模型 ➡️ （未解决）双端队列