题解 P1638 【逛画展】
引领天下
2019-02-13 19:01:51
看了一下前面的题解都麻烦了，所以来一发简单的题解
因为是要求看的画是连续的，所以可以考虑尺取法（双指针法）
既然要求要看到M位画家的画，我们可以考虑维护一个区间[l,r]，保证这个区间是含有M位画家且以l开头最小的区间，则如果想更新答案获得更小区间，只能右移l，而不能左移r。
为什么呢？
考虑反证法。
假设有一个区间[l,r-k]比[l,r]更优，则这段区间会在r
=r-k的时候就被更新，所以左移r无用。
所以r就满足单调性（只增不减），可以用尺取法做。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int n,m,a[MAXN],ans,b[MAXN],cnt,ansl,ansr;
inline void I(int x){if(b[x]==0)cnt++;b[x]++;}//加入第x位画家的画
inline void D(int x){if(b[x]==1)cnt--;b[x]--;}//删除第x位画家的画
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf ("%d",&a[i]);
ans=n;
for(int r=1,l=1;r<=n;r++){
I(a[r]);//首先插入a[r]的画
while(true){
D(a[l]);//先删a[l]的画
if(cnt==m)l++;//如果删了没事，加l
else{I(a[l]);break;}//删了有事，还留着
}
if(cnt==m&&r-l+1<ans)ans=r-l+1,ansl=l,ansr=r;
}
if (ansl!=0)printf ("%d %d",ansl,ansr);
else printf ("1 %d",n);//输出+特判：选择任意一个≤n的区间不满足要求，则只好选择区间[1,n]
return 0;
}
```