【POJ 3320】【尺取法】Jessica's Reading Problem【暑期 No.2】

题意：

       为了准备考试，Jessica开始读一本很厚的课本。要想通过考试，必须把课本中所有的知识点都掌握。这本书总共有P页，第 i 页恰好有一个知识点ai（每个知识点都有一个整数编号）。全书中同一个知识点可能会被多次提到，所以她希望通过阅读其中连续的一些页把所有的知识点都覆盖到。给定每页写到的知识点，请求出要阅读的最少页数。

 

分析：

        首先肯定需要求出总共有多少门不同的课，因此用set来进行去重.

        然后再用 map[课程] 来记录在我选的这段区间中，选了多少次这门课程.

        用sum来记录我当前已经选了多少门不同的课程了，然后进行尺取，每次都r++直到sum == 总课程数，达到之后，与ans比较最小值，然后再l++，并且判断sum是否需要 -1.

 

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <set>
#include <map> 
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int SIZE = 1e6+10;

int n;
int a[SIZE];
set<int>all;   //用来去重 
map<int,int>cnt;  //用来标记这一页被复习了几次 

int main()
{
	while(~scanf("%d",&n))
	{
		rep(i,1,n)
		{
			scanf("%d",&a[i]);
			all.insert(a[i]);
			cnt[a[i]] = 0;
		}
		int l = 1,r = 0;
		int len = all.size();
		int sum = 0;
		int ans = 1e9;
		while(l <= n && r<=n)
		{
			while(sum < len && r <= n)
			{
				r++;
				if(cnt[a[r]] == 0)
					sum++;
				cnt[a[r]]++;
			}
			if(sum == len)
				ans = min(ans,r-l+1);
			else
				break;
			cnt[a[l]]--; 
			if(cnt[a[l]] == 0) sum--;
			l++;
		}	
		printf("%d\n",ans);
	}
	return 0;	
}