逛画展

ゝ一世哀愁。 2022-02-15 00:55 160阅读 0赞

## 1. 题目简介 ##

博览馆正在展出由世上最佳的 M 位画家所画的图画。

wangjy想到博览馆去看这几位大师的作品。

可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，a和b，代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画，而门票的价钱就是一张图画一元。

为了看到更多名师的画，wangjy希望入场后可以看到所有名师的图画(至少各一张)。

可是他又想节省金钱。。。

作为wangjy的朋友，他请你写一个程序决定他购买门票时的 a 值和 b 值。

#### 输入格式 ####

第一行包含两个整数 N 和 M，表示图画总数和画家数量。

第二行包含 N 个整数，它们都介于 1 和 M 之间，代表画作作者的编号。

#### 输出格式 ####

输出两个整数 a 和 b。

数据保证有解，如果存在多个解，则输出 a 最小的那个解。

#### 数据范围 ####

1≤N≤1061≤N≤106

#### 输入样例： ####

12 5
    2 5 3 1 3 2 4 1 1 5 4 3

#### 输出样例： ####

2 7

<table> 
 <tbody> 
  <tr> 
   <td> 难度： <span>简单</span> </td> 
  </tr> 
  <tr> 
   <td> 时/空限制： 1s / 64MB </td> 
  </tr> 
  <tr> 
   <td> 总通过数： 29 </td> 
  </tr> 
  <tr> 
   <td> 总尝试数： 47 </td> 
  </tr> 
  <tr> 
   <td> 来源： USACO </td> 
  </tr> 
 </tbody> 
</table>

## 2. 思路简介 ##

记录一下【秦淮岸】大佬的思路解析：  
程序=算法+数据结构.这道题目我们可以利用尺取法(也就是双指针法),当然我们也可以使用数据结构单调队列.  
看到这道题目,我们显然要分析这道题目为什么可以用单调队列.

首先我们发现,对于一幅名画而言,如果我当前的候选门票区间,在候选区间的最左端,已经有了和它属于同一个画家的名画的话,那么我们显然是可以抛去之前的老画了,从原来的\[l,r\]–>\[l+1,r+1\]  
因为我现在还没有找到满足所有名家的画都看过的条件,那么我们显然是还要往后找的,但是我要求票价最小,所以说我们必须将\[l,r\]–>\[l+1,r+1\].  
因为\[l,r\]–>\[l+1,r+1\],不同名家画数量一样多,而且\[l+1,r+1\]比\[l,r\]更加具有潜力,拓展性

综上所述,我们这道题目一个隐藏的单调性质就出现了,在加上区间问题,必然具有队列性质,因此我们可以确定数据结构,单调队列无疑了.

结构梳理  
如果说队头名画,在队列中还有另外一副和它同属一个画家,那么显然队头必须抛弃.  
对于每一幅名画,它都可以入队.  
对于每一个候选区间,如果它所有类型的名画都集齐了,那么我们就要统计区间费用.

## 3. 详细代码 ##

#include <iostream>
    #include <queue>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    int a[N], b[N];
    int ansa, ansb, ans = 1e7;
    int cnt = 0;
    deque<int> dque;
    
    
    int main()
    {
        
        memset(b, 0, sizeof(b));
        
        int n, m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
            cin >> a[i];
        for(int i = 1;i <= n;i++)
        {
        
            if(!b[a[i]])
                cnt++;
            dque.push_back(i); // 选第i幅画
            b[a[i]]++;		   // 记录当前选的画家画的个数
            while(b[a[dque.front()]] >= 2) // 前面的节点可有可无时，就出队
            {
        
                b[a[dque.front()]]--;
                dque.pop_front();
            }
            if(cnt >= m && dque.back() - dque.front() + 1 < ans) // 如果当前区间内名画数目满足，要求就记录答案
            {
        
                ans = dque.back() - dque.front() + 1;
                ansa = dque.front();
                ansb = dque.back();
            }
        }
        cout << ansa << " " << ansb << endl;
        return 0;
    }