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

Jessica's Reading Problem

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 8787	Accepted: 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

2      

  今天開始學算法系列 -- 尺取法 2015-02-28 09:54:49

分類： C/C++

轉載一段講解  

     我們先來介紹一下尺取法。尺取法，顧名思義，像尺子一樣，一塊一塊的截取。是不是解釋的有點讓人納悶～。。沒關系，下面我們通過這個題目來體會尺取法的魅力。

題目翻譯：

　　給定長度為n的數列整數a0,a1,a2,a3 ..... an-1以及整數S。求出綜合不小于S的連續子序列的長度的最小值。如果解不存在，則輸出0。

　　限制條件：

　　　　10<n<10^5 <="" p="">

　　　　0<ai<10^4 <="" p="">

　　　　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]]為０時，tail和cnt才會＋＋

1 /*************************************************************************
 2     > File Name: code/poj/3320.cpp
 3     > Author: 111qqz
 4     > Email: [email protected] 
 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
26 using namespace std;
27 #define For(i, n) for (int i=0;i<int(n);++i)  
28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 const int N = 1E6+7;
32 int a[N];
33 int p;
34 void solve ()
35 {
36     set<int>se;
37     for ( int i = 1 ; i <= p ; i++)
38     {
39     scanf("%d",&a[i]);
40     se.insert(a[i]);
41     }
42     int total = se.size();
43     map<int,int> cnt;
44     int ans = p ;
45     int head = 1 ;
46     int tail = 1 ;
47     int sum = 0 ;
48     while (1)
49     {
50     while (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 }
72 int 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 }      

View Code

轉載于:https://www.cnblogs.com/111qqz/p/4836670.html