POJ 3320: Jessicas Reading Problem

Jessica’s Reading Problem （ POJ No.3320）
　　为了准备考试， Jessica 开始读一本很厚的课本。要想通过考试，必须把课本中所有的知识点都掌握。这本书总共有 P 页，第 i 页恰好有一个知识点 ai（每个知识点都有一个整数编号）。全书中同一个知识点可能会被多次提到，所以她希望通过阅读其中连续的一些页把所有的知识点都覆盖到。给定每页写到的知识点，请求出要阅读的最少页数。
限制条件
　　1 ≤ P ≤ 10^6
输入：
　　P = 5
　　a = {1, 8, 8, 8, 1}
输出：
　　2

解题思路：假设从某一页s开始阅读，为了覆盖所有的知识点读到t页，这样的话如果从s+1开始阅读，那么必须读到t’>=t位置，故可以用尺取法。

int P; //页数
int a[P];  //可能重复的P个知识点
int count[KP]; //知识点计数数组

void solve{
    set<int> all_knowledge；

    for(int i = 0; i < T; i++)
        all_knowledge.insert(a[i]);

    knowledge_total = all_knowledge.size();

    //尺取法
    int start = 0;
    int end = 0;
    int min_pages = P;

    while(1){
        while(end < P && knowledge_cnt < knowledge_total) {
            if(count[a[end++]]++ == 0)
                knowledge_cnt++;
        }

        if(knowledge_cnt < knowledge_total) {
            break;
        }

        min_pages = MIN(min_pages,end - start);

        if(--count[a[start++]] == 0) {
            knowledge_cnt--;
        }
    }

    cout << min_pages<<endl;
}