Posted on 2009-08-27 16:50
Uriel 閱讀(624)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ
校個(gè)人賽遇到才知道最小表示法。。經(jīng)典，強(qiáng)大，可惜還沒完全懂，只是勉強(qiáng)照搬。
/**//*Problem: 1509 User: Uriel
Memory: 144K Time: 16MS
Language: C Result: Accepted*/
#include<stdio.h>
#include<string.h>
int min(int a, int b)
{
return a <= b ? a : b;
}
int MinimumRepresentation(char *s, int l)
{
int i = 0, j = 1, k = 0, t;
while (i < l && j < l && k < l)
{
t = s[(i + k)%l] - s[(j + k)%l];
if (!t) ++ k;
else
{
if (t > 0) i = i + k + 1;
else j = j + k + 1;
if (i == j) ++j;
k = 0;
}
}
return min(i,j);
}
int x,len,i,t;
char str[10010];
int main()
{
scanf("%d",&t);
getchar();
while(t--)
{
memset(str,0x00,sizeof(str));
scanf("%s",str);
len=strlen(str);
x=MinimumRepresentation(str,len);
printf("%d\n",x+1);
}
return 0;
}