poj 3320

水题

主要是发现poj一堆练这个的不明所以所以练练

http://poj.org/problem?id=3320

思路很简单找到包含所有id的一个区间对那个区间进行缩小注意要count最少的出连续的个数

 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     while(sumIdea != 0)// 寻找最短包含所有知识点区间 
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     //end++,mymap[ a[end] ]++，并判断mymap[ a[start] ]是否大于1，如果大于，start++，直到不大于为止，并更新 res。
26     //重复 直到end>P 
27     while(end <= P)
28     {
29         mymap[idea[end++]]++;
30         while(mymap[idea[start]] > 1)
31             mymap[idea[start++]]--;
32         res=min(res,end-start);
33     }
34     return res;
35 }
36 
37 int main()
38 {
39     scanf("%d",&P);
40     for(int i=1;i <= P;++i)
41     {
42         scanf("%d",idea+i);
43         myset.insert(idea[i]);//用set去重
44         mymap[idea[i]]=0;
45     }
46     printf("%d
",Solve());
47 }

View Code