题解 P1638 【逛画展】

发表于 更新于 阅读次数： Waline：
P1638 【逛画展】题解。

看了一下前面的题解都麻烦了，所以来一发简单的题解

因为是要求看的画是连续的，所以可以考虑尺取法（双指针法）

既然要求要看到M位画家的画，我们可以考虑维护一个区间[l,r]，保证这个区间是含有M位画家且以l开头最小的区间，则如果想更新答案获得更小区间，只能右移l，而不能左移r。

为什么呢？

考虑反证法。

假设有一个区间[l,r-k]比[l,r]更优，则这段区间会在r
=r-k的时候就被更新，所以左移r无用。

所以r就满足单调性（只增不减），可以用尺取法做。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}