题目描述
博览馆正在展出由世上最佳的 M 位画家所画的图画。
wangjy想到博览馆去看这几位大师的作品。
可是,那里的博览馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字,a和b,代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画,而门票的价钱就是一张图画一元。
为了看到更多名师的画,wangjy希望入场后可以看到所有名师的图画(至少各一张)。
可是他又想节省金钱。。。
作为wangjy的朋友,他请你写一个程序决定他购买门票时的 a 值和 b 值。
输入格式
第一行包含两个整数 N 和 M,表示图画总数和画家数量。
第二行包含 N 个整数,它们都介于 1 和 M 之间,代表画作作者的编号。
输出格式
输出两个整数 a 和 b。
数据保证有解,如果存在多个解,则输出 a 最小的那个解。
数据范围
1≤N≤106,
1≤M≤2000
输入样例:
12 5
2 5 3 1 3 2 4 1 1 5 4 3
输出样例:
2 7
算法1
(滑动窗口) $O(n)$
时间复杂度分析:每个元素出一次,进一次
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,h,k,l,r,ans=1e9+7,cnt[2005],q[1000005];
int main()
{
scanf("%d%d",&n,&m);
h=1;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(cnt[x]==0)
++k;
++cnt[x];
q[i]=x;
while(h<i&&k==m)
{
if(ans>i-h+1){
ans = i-h+1;
l=h,r=i;
}
--cnt[q[h]];
if(cnt[q[h]]==0) k--;
h++;
}
}
printf("%d %d\n",l,r);
return 0;
}