poj 3320(尺取法)

传送门:Problem 3320

参考资料：

　　[1]:挑战程序设计竞赛

题意：

　　一本书有 P 页，每页都有个知识点a[i]，知识点可能重复，求包含所有知识点的最少的页数。

题解：

　　相关说明：

　　　　设以a[start]开始的最初包含所有知识点的最少连续子序列为a[start,....,end];

　　　　mymap[ a[i] ] : 知识点 a[i] 在当前最少连续子序列中出现的次数。

　　(1):求出所需复习的知识点总个数。

　　(2):求出最先包含所有知识点的最少页数a[start,........,end]。

　　(3):end++,mymap[ a[end] ]++，并判断mymap[ a[start] ]是否大于1，如果大于，start++，直到不大于为止，并更新 res。

　　(4):重复(3)过程，直到end > P。

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<set>
 4 #include<map>
 5 using namespace std;
 6 const int maxn=1e6+50;
 7 
 8 int P;
 9 int idea[maxn];
10 set<int>myset;
11 map<int ,int >mymap;
12 
13 int Solve()
14 {
15     int sumIdea=myset.size();//步骤(1)
16     int start=1,end=1;
17     while(sumIdea != 0)//步骤(2) 
18     {
19         sumIdea -= (mymap[idea[end]] == 0 ? 1:0);
20         mymap[idea[end++]]++;
21         while(mymap[idea[start]] > 1)
22             mymap[idea[start++]]--;
23     }
24     int res=end-start;
25     while(end <= P)//重复执行步骤(3)(4) 
26     {
27         mymap[idea[end++]]++;
28         while(mymap[idea[start]] > 1)
29             mymap[idea[start++]]--;
30         res=min(res,end-start);
31     }
32     return res;
33 }
34 
35 int main()
36 {
37     scanf("%d",&P);
38     for(int i=1;i <= P;++i)
39     {
40         scanf("%d",idea+i);
41         myset.insert(idea[i]);//set去重
42         mymap[idea[i]]=0;
43     }
44     printf("%d
",Solve());
45 }

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<set>
 4 #include<map>
 5 using namespace std;
 6 const int maxn=1e6+50;
 7 
 8 int P;
 9 int idea[maxn];
10 set<int>myset;
11 map<int ,int >mymap;
12 
13 int Solve()
14 {
15     int sumIdea=myset.size();
16     int start=1,end=1;
17     int total=0;
18     int res=0;
19     while(1)
20     {
21         while(end <= P && total < sumIdea)
22             total += ((mymap[idea[end++]]++) == 0 ? 1:0);
23         
24         if(total < sumIdea)//如果 total < sumIdea,说明跳出上一个while()的条件为 end > P 
25             break;
26         res=(res == 0 || res > end-start ? end-start:res);
27         if(--mymap[idea[start++]] == 0)
28             total--;
29     }
30     return res;
31 }
32 
33 int main()
34 {
35     scanf("%d",&P);
36     for(int i=1;i <= P;++i)
37     {
38         scanf("%d",idea+i);
39         myset.insert(idea[i]);//set去重
40         mymap[idea[i]]=0;
41     }
42     printf("%d
",Solve());
43 }

挑战程序设计竞赛