Description
Jessica's a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.
A very hard-working boy had manually indexed for her each page of Jessica's text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.
Input
The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica's text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.
Output
Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.
Sample Input
5 1 8 8 8 1
Sample Output
2
题意就是给一个数列，找到一个最小的区间，包含这个数列中出现的所有元素。这类连续的区间问题，
很多都可以用这种尺取法线性的扫描。
思路: 尺取法，能用尺取法的原因：假设当前a[s],a[s+1],,,,,a[t]包含只有种类，当s=s+1时，要仍然包含所有种类，则t'>=t，
关键是set和map的使用 ，set相当于集合,map相当于数组. 这里先普及一下set的知识,因为我也是第一次用: 1、set会根据特定的排序准则自动将元素排序，set中元素不允许重复,search操作效率会很高O(log n)2、关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出 数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树 (Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。
因为是排序的，所以set中的元素不能被修改，只能删除后再添加。
3、
set中常用的方法
begin() ,返回set容器的第一个元素
end() ,返回set容器的最后一个元素
clear() ,删除set容器中的所有的元素
empty() ,判断set容器是否为空
max_size() ,返回set容器可能包含的元素最大个数
size() ,返回当前set容器中的元素个数
rbegin ,返回的值和end()相同
rend() ,返回的值和rbegin()相同
count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，
这样就变成了判断某一键值是否在set出现过了。
下面看代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#define N 1000010
using namespace std;
int a[N];
int main()
{ int p;
int i;
while(scanf("%d",&p)!=EOF)
{ for(i=0;i<p;i++)
scanf("%d",&a[i]);
set<int>ss;
map<int,int>mp;
for(i=0;i<p;i++)
ss.insert(a[i]);//因为set中的元素有序且不允许重复,所以我们可以查到需要出现的种类有几个.
int n=ss.size();
int s=0,t=0,sum=0,res=p;
while(1)
{ while(t<p&&sum<n)
{ if(mp[a[t]]==0)//如果当前种类为出现过就+1，并且总种类sum+1；
{
sum++;
mp[a[t]]++;
t++;//区间右端点右移
}
else
{ mp[a[t]]++;//如果已经出现过，则出现次数+1；
t++;
}
}
if(sum<n)
break;
res=min(res,t-s);//更新最小长度
mp[a[s]]--;//左端点右移前先把该种类出现的次数-1；
if(mp[a[s]]==0)//如果此时该种类出现的次数为0，则出现的总种类-1；
{ sum--;
}
s++;//左端点右移;
}
printf("%d\n",res);
}
}
更多推荐
POJ 3320 Jessica's Reading Problem 尺取法+set
发布评论