ACM 尺取法 poj 3320

最近學一些簡單的技巧，這個尺取法就是其一

http://poj.org/problem?id=3320

題意：

書一共p頁，第i頁有一個知識點a[i],同一個知識點可以多次出現，想要讀連續的書頁把所有的知識點覆寫，求要讀的最少的頁數

思路：

首先set記錄所有的知識點

假設從第s頁到第t頁剛好覆寫所有知識，記錄下一個answear,那麼s++繼續增大t直到再次覆寫所有的知識，就又得到一個answear,去兩個answear的最小值，同理繼續增大s

/*這裡是為了給一個尺取法的模闆架構*/

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
#define INF 0x0fff ffff

#define MAXN 1000003

int p,a[MAXN];


void solve()
{
    int i,n,res=p;
    set<int>all;
    for(i=0;i<p;i++)
    {
        scanf("%d",&a[i]);
        all.insert(a[i]);
    }
    n=all.size();

    int s=0,t=0,num=0;
    map<int,int>cnt;
    for(;;)
    {
        while(t<p&&num<n)
        {
            if(cnt[a[t++]]++==0)/*出現新的*/
                num++;
        }
        if(num<n)break;
        res=min(res,t-s);
        if(--cnt[a[s++]] == 0)
            num--;
    }

    printf("%d\n",res);
}

int main()
{
    while(scanf("%d",&p)!=EOF)
    {
        solve();
    }
}