当前位置: 首页 > 工具软件 > Jessica > 使用案例 >

POJ 3320: Jessicas Reading Problem

能业
2023-12-01

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;
}
 类似资料:

相关阅读

相关文章

相关问答