今天也是闲来无事,想去做一下,之前学过的某个题型,但是在中间突然发现了这个题,那时候年少无知,做不出来,今天也是很轻松的用双指针轻松拿捏,因此发帖。
传送门:逛画展
题解:我们完全可以用滑动窗口的思想,去用两个指针去维护一个区间范围,左指针固定不动,移动右指针,直到右指针移动到的位置,能够把每一个画家的画作都囊括,然后慢慢移动左指针,如果当左指针目前位置,在这个区间内出现过两次,那么就可以减少一下长度,然后反复和我们自己设定的minn最小长度进行比较,直到找出最短长度
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int ans[1000005];
int flag=0;
int minn=0x3f3f3f3f;
int len=0;
int start1,end1;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];int l=1,r=1;for(r=1;r<=n;r++){if(ans[a[r]]==0)flag++;ans[a[r]]++;len++;if(flag==m){while(ans[a[l]]>1){ans[a[l]]-=1;l+=1;len-=1;}if(len<minn){minn=len;start1=l;end1=r;}}}printf("%d %d\n",start1,end1);return 0;
}