Jessica's 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 (只要阅读第1页和第2页即可)

---

分析：

我们假设从某一 页s开始阅读,为了覆盖所有的知识点需要阅读到t。这样的话可以知道如果从s+1开始阅读的话，那么必须阅读到t'≥t页

为止。由此这题也可以使用尺取法。

在某个区间[s,t]已经覆盖了所有的知识点的情况下，下一个区间[s+1，t'](t'≥t)要如何求出呢?

所有的知识点都被覆盖等价于每个知识点出现的次数都不小于1

由以上的等价关系，我们可以用二叉树等数据结构来存储[s,t]区间上每个知识点的出现次数，这样把最开头的页s去除后便可以判断[s+1,t]是否满足条件。

从区间的最开头把s取出之后，页s上书写的知识点的出现次数就要减一，如果此时这个知识点的出现次数为0了，在同一个知识点再次出现前，不停将区间末尾向后推进即可。每次在区间末尾追加页时将页t上的知识点的出现次数加1,这样就完成了下一个区间上各个知识点出现次数的更新，通过重复这一-操作可以以O(PlogP)的复杂度求出最小的区间。

实现：

#include<iostream>
#include<set>
#include<map>
#include<vector>
using namespace std;
int main() {
	int n;
	cin>>n;
	set<int> st;
	vector<int> a(n);
	for(int i=0; i<n; ++i) {
		cin>>a[i];
		st.insert(a[i]);
	}
	int m=st.size();
	map<int,int>count;
	int s=0,t=0,sum=0,res=n;
	while(1) {
		while(t<n&&sum<m)
			if(!count[a[t++]]++)
				sum++;
		if(sum<m)
			break;
		res=min(res,t-s);
		if((--count[a[s++]])==0)
			sum--;
	}
	cout<<res;
	return 0;
}