逛画展

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

一行两个整数 a,b。

样例 #1

样例输入 #1

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

样例输出 #1

2 7

这个题目没什么好讲的，精髓在于左右两端点的枚举以及一些小细节的处理
直接上代码

#include<iostream>

using namespace std;

int m,n;
int a[2000005];
int cntl,cntr,num=0x3f3f3f3f,cnt;
int t[20005];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=1,r=1;
	t[a[1]]=1;
	cnt=1;
	while(1){
		while(r<n&&cnt<m){//细节1
			if(t[a[r+1]]==0) cnt++;//细节2
			t[a[++r]]++;
		} 
		//cout<<r<<endl; —————> 调试的（1）
		if(cnt<m) break;//细节3
		while(l<r&&t[a[l]]>1){
			t[a[l++]]--;
		}
		/*cout<<"l="<<endl; —————> 调试的（2）
		cout<<l<<endl;*/
		if((r-l+1)<num){//细节4
			cntl=l,cntr=r,num=r-l+1;
		}
		cnt--;
		t[a[l++]]--;
	}
	cout<<cntl<<" "<<cntr;
}