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;
}