USACO 5.5 Hidden Password(搜索+优化)

水了好几下。

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

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

 /*
ID: cuizhe
LANG: C++
TASK: hidden
*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
int que1[],que2[];
char str[];
int main()
{
int i,len,minz,num,tnum,temp;
char ch;
freopen("hidden.in","r",stdin);
freopen("hidden.out","w",stdout);
scanf("%d",&len);
for(i = ;i < len;)
{
scanf("%c",&ch);
if(ch != '\n')
str[i++] = ch;
}
for(i = len;i < *len;i ++)
{
str[i] = str[i-len];
}
minz = ;
num = ;
for(i = ;i < len;i ++)
{
if(minz > str[i]-'a')
{
num = ;
minz = str[i]-'a';
que1[num++] = i;
}
else if(minz == str[i]-'a')
{
if(i != &&str[i-]-'a' == minz)
continue;//优化1
que1[num++] = i;
}
}
for(temp = ;;temp ++)
{
if(num == ) break;
minz = ;
for(i = ;i < num;i ++)
{
if(minz > str[que1[i]+]-'a')
{
minz = str[que1[i]+]-'a';
tnum = ;
que2[tnum++] = que1[i]+;
}
else if(minz == str[que1[i]+]-'a')
{
if(que2[tnum-] >= que1[i]+ -temp)
continue;//优化2
que2[tnum++] = que1[i]+;
}
}
for(i = ;i < tnum;i ++)
que1[i] = que2[i];
num = tnum;
}
printf("%d\n",que1[]-temp);
return ;
}
上一篇:iOS 5个Xcode开发调试技巧


下一篇:IOS开发之xcode 快捷键