AcWing 651. 逛画展
原题链接
简单
作者:
BQY
,
2022-08-16 20:41:14
,
所有人可见
,
阅读 228
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],flag[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int cnt=0,maxn=1e8;
int l=0,r=0;
for(int i=1,j=0;i<=n;i++)// 暴力枚举左端点
{
if(i>1)
{
flag[a[i-1]]--; // 窗口左移吐出原来的第一个数
if(flag[a[i-1]]==0)cnt--; // 如果吐出后变为0说明画作数量要减1
}
while(j<=n&&cnt<m) // 区间满足的性质
{
j++;
if(flag[a[j]]==0) cnt++;
flag[a[j]]++;
}
if(cnt==m&&j<=n)
{
if(j-i+1<maxn)
{
maxn=j-i+1;
l=i;
r=j;
}
}
}
cout<<l<<" "<<r<<endl;
return 0;
}