USACO 5.5 Hidden Password(搜索+优化)

水了好几下。

优化1：开始初始化的时候，如果左边那个也是最小值，那么此点就不用进队了。

优化2:如果队列里的位置，已经超过了后面位置的初始位置，那么后面这个位置也没用了。

 1 /*
 2 ID: cuizhe
 3 LANG: C++
 4 TASK: hidden
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <string>
 9 #include <cmath>
10 #include <algorithm>
11 using namespace std;
12 int que1[200001],que2[200001];
13 char str[300001];
14 int main()
15 {
16     int i,len,minz,num,tnum,temp;
17     char ch;
18     freopen("hidden.in","r",stdin);
19     freopen("hidden.out","w",stdout);
20     scanf("%d",&len);
21     for(i = 0;i < len;)
22     {
23         scanf("%c",&ch);
24         if(ch != '
')
25         str[i++] = ch;
26     }
27     for(i = len;i < 2*len;i ++)
28     {
29         str[i] = str[i-len];
30     }
31     minz = 10000;
32     num = 0;
33     for(i = 0;i < len;i ++)
34     {
35         if(minz > str[i]-'a')
36         {
37             num = 0;
38             minz = str[i]-'a';
39             que1[num++] = i;
40         }
41         else if(minz == str[i]-'a')
42         {
43             if(i != 0&&str[i-1]-'a' == minz)
44             continue;//优化1
45             que1[num++] = i;
46         }
47     }
48     for(temp = 0;;temp ++)
49     {
50         if(num == 1) break;
51         minz = 10000;
52         for(i = 0;i < num;i ++)
53         {
54             if(minz > str[que1[i]+1]-'a')
55             {
56                 minz = str[que1[i]+1]-'a';
57                 tnum = 0;
58                 que2[tnum++] = que1[i]+1;
59             }
60             else if(minz == str[que1[i]+1]-'a')
61             {
62                  if(que2[tnum-1] >= que1[i]+1 -temp)
63                  continue;//优化2
64                  que2[tnum++] = que1[i]+1;
65             }
66         }
67         for(i = 0;i < tnum;i ++)
68         que1[i] = que2[i];
69         num = tnum;
70     }
71     printf("%d
",que1[0]-temp);
72     return 0;
73 }