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 }