---
title: "逛画展"
created: 2025-11-28
tags:
  - 算法
---

# 逛画展

## 题目 [逛画展](https://www.acwing.com/problem/content/description/653/)

![[image-fd992d6b.png]]

## 思路分析

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

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

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

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

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

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

![[逛画展-73e5646d.gif]]

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/队列/蚯蚓|蚯蚓]] 🏠 [[00-刷题理模型]] ➡️ [[（未解决）双端队列|（未解决）双端队列]]