目录

一、题目回顾

题目描述

输入格式

输出格式

二、代码与思路

 题目分析

解题思路

代码

复杂度分析

注意事项

---

一、题目回顾

题目描述

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

游客在购买门票时必须说明两个数字，和，代表他要看展览中的第 幅至第 幅画（包含 ）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 ，数据保证一定有解。

若存在多组解， 输出    最小的那组 。

输入格式

第一行两个整数 ，分别表示博览馆内的图画总数及这些图画是由多少位名师所绘画的。

第二行包含 个整数 ，代表画第  幅画的名师的编号。

输出格式

一行两个整数 。

二、代码与思路

 题目分析

这道题目要求我们找到一个最短的连续子区间，使得这个区间内包含所有m位画家的作品。如果有多个这样的区间，我们选择左端点最小的那个。

解题思路

我们可以使用滑动窗口（双指针）的方法来解决这个问题：

1. 使用两个指针和表示当前窗口的左右边界。
2. 维护一个计数器，记录当前窗口中不同画家的数量。
3. 使用一个数组来记录当前窗口中每个画家的出现次数。
4. 右指针不断向右移动，扩展窗口，直到窗口中包含所有位画家。
5. 当窗口中包含所有画家时，尝试移动左指针，尽可能缩小窗口大小，同时保持窗口中仍然包含所有画家。
6. 在每次找到符合条件的窗口时，检查是否比当前最优解更优（窗口更小，或者窗口大小相同但左端点更小）

代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
static const int N=1e6+10;
int n,m,a[N],ansr=0,ansl=N,sum=N;
int tong[N];

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
    }
    
    int l=1,r=1,ans=0,cnt=0;
    while(r<=n) 
    {
        if(tong[a[r]]==0) 
        {  // 遇到新的画家
            cnt++;
        }
        tong[a[r]]++;  // 记录出现次数
        ans++;  // 窗口大小增加
        
        // 尝试缩小左边界
        while(tong[a[l]]>1) 
        {  // 如果左边界画家的作品在窗口中出现多次
            ans--;  // 窗口大小减小
            tong[a[l]]--;  // 减少计数
            l++;  // 移动左边界
        }
        
        // 如果包含所有画家且窗口更小
        if(cnt==m && ans<sum) 
        {
            ansl=l;
            ansr=r;
            sum=ans;
        }
        r++;  // 移动右边界
    }
    cout<<ansl<<" "<<ansr;
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，其中n是图画的总数。每个元素最多被访问两次（一次被右指针，一次被左指针）。
• 空间复杂度：O(m)，用于存储每个画家的出现次数。

注意事项

1. 初始化时ansl要设为一个较大的值（如N），以便后续比较。
2. 在移动左指针时，只有当某个画家的作品在窗口中出现多次时才移动，这样可以保证窗口中始终包含所有画家。
3. 题目要求当有多个解时选择x最小的那个，因此在ans==sum时不需要更新答案，这保证了我们保留的是最先找到的解（即x最小的解）。