poj3320 Jessica's Reading Problem

Jessica's Reading Problem

 POJ - 3320 

题目大意：

课本有n页，第i页有一个知识点a[i]，要阅读连续的一些页把所有知识点都覆盖到，求阅读的最少页数

Sample Input

5
1 8 8 8 1

Sample Output

2

/*
    尺取法：
    做法类似于poj3061
*/
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define maxn 1000010
int n,a[maxn],s=1,t,ans,sum,last;
map<int,bool>v;
map<int,int>vis;
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!v[a[i]]){
            v[a[i]]=1;
            last++;
        }
    }
    ans=n+1;
    while(1){
        while(t<n&&sum<last){
            t++;
            if(!vis[a[t]])sum++;
            vis[a[t]]++;
        }
        if(sum<last)break;
        ans=min(ans,t-s+1);
        vis[a[s]]--;
        if(vis[a[s]]==0)sum--;
        s++;
    }
    printf("%d",ans);
}