poj 3320 Jessica's Reading Problem (尺取法)

Jessica’s Reading Problem

Time Limit	Memory Limit	Total Submissions	Accepted
1000MS	65536K	8787	2824

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

今天开始学算法系列 – 尺取法 2015-02-28 09:54:49

分类： C/C++

转载一段讲解

我们先来介绍一下尺取法。尺取法，顾名思义，像尺子一样，一块一块的截取。是不是解释得有点让人纳闷？没关系，下面我们通过这个题目来体会尺取法的魅力。
题目翻译：
　　给定长度为 n 的数列整数 a0,a1,a2,a3 ….. an-1 以及整数 S。求出总和不小于 S 的连续子序列的长度的最小值。如果解不存在，则输出 0。
　　限制条件：
　　　　10
　　　　0
　　　　S<10^8
这里我们拿第一组测试数据举例子，即 n=10, S = 15, a = {5,1,3,5,10,7,4,9,2,8}
　　这幅图便是尺取法怎么"取"的过程了。
　　整个过程分为 4 步：
　　　　1.初始化左右端点
　　　　2.不断扩大右端点，直到满足条件
　　　　3.如果第二步中无法满足条件，则终止，否则更新结果
　　　　4.将左端点扩大1，然后回到第二步
用尺取法来优化，使复杂度降为了O(n)。
最后，再给一个尺取法的定义以便更好理解：返回的推进区间开头和结尾，求满足条件的最小区间的方法称为尺取法。
以上为网上关于尺取法的原理介绍，还是比较好理解的，形如蚯蚓的爬动。

　　然后这道题可以先用set ，统计出不同的知识点有多少个，总是记为total

　　然后根据一段区间内的知识点数目sum是否达到total来移动两个pointer head 和tail

　　因为知识点的标号比较大，数组下标存不下，所以开个 map 来统计相应知识点出现的数量…

　　然后还有个…

　　误以为if (cnt[a[tail++]]++==0) sum++；和

　　if (cnt[a[tail]]==0)

　　{

　　　　sum++;

　　　　cnt[a[taill]]++;

　　　　tail++;

　　}

　　是等价的。

幸好没去队群里问，不然又要被嘲讽一番了。

区别在于：前者无论 cnt[a[tail]] 是否为 0，tail 和 cnt 都会 ++；

而后者只有在 cnt[a[tail]] 为 0 时，tail 和 cnt 才会 ++

代码实现

 1/*************************************************************************
 2	> File Name: code/poj/3320.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com
 5	> Created Time: 2015年09月24日 星期四 19时33分20秒
 6 ************************************************************************/
 7
 8#include<iostream>
 9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N = 1E6+7;
32int a[N];
33int p;
34void solve ()
35{
36set<int>se;
37for ( int i = 1 ; i <= p ; i++)
38{
39scanf("%d",&a[i]);
40se.insert(a[i]);
41}
42int total = se.size();
43map<int,int> cnt;
44int ans = p ;
45int head = 1 ;
46int tail = 1 ;
47int sum = 0 ;
48while (1)
49{
50while (tail<=p&&sum<total)
51{
52    // cout<<"ajhhh"<<endl;
53 //  if (cnt[a[tail++]]++ ==0) sum++;
54     if (cnt[a[tail]]==0)
55    {
56
57	sum++;
58    }
59 		cnt[a[tail]]++;
60         	tail++;
61
62
63	     cout<<"total"<<total<<endl;
64	}
65	if (sum<total) break;
66	ans = min (ans ,tail - head);
67	if (--cnt[a[head++]]==0) sum--;
68
69    }
70    printf("%d\n",ans);
71}
72int main()
73{
74  #ifndef  ONLINE_JUDGE
75   freopen("in.txt","r",stdin);
76  #endif
77   while (scanf("%d",&p)!=EOF)
78    {
79	solve();
80    }
81
82
83 #ifndef ONLINE_JUDGE
84  fclose(stdin);
85  #endif
86	return 0;
87}

相关文章