1550: AA
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 88 Solved: 26
[ Submit][ Status][ Web Board]
Description
其实第一次听说要出题目我是拒绝的，因为，你不能让我出，我就马上去出，我要试一下，因为我不愿意出完了以后再加一些案例上去，然后题目duang的一下就被AC了。现在要求对字符串进行环状左移操作，每次向左移动一个位置。例如：对duang进行操作，得到的全部字符串为：
duang
uangd
angdu
ngdua
gduan
输出得到最小字典序的字符串的最小移动次数。
Input
输入一个数T(1<=T<=100),表示接下来有T行字符串；输入字符串S，S的长度为L（5<=l<=100000）。
Output
输出一个数字，表示为得到最小字典序的字符串的最小移动次数。
Sample Input
2
baabaa
alabala
Sample Output
1
6
【解析】
这道题我提交了好多次都是超时...但是呢我觉得做题目嘛主要是学东西..我是用map，结构体还有用刘汝佳老师书上的方法也试了一下还是超时...此处附上我的超时代码...其实有的时候我们不能真的为了AC而去AC。还可以直接比较..还有就是当我们用map<string,int>的时候是按照string的最小字典序来排列的所以我们也可以用map
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
struct E
{string zi;//结构体存储int b;
};
bool cmp(E a,E b)
{return (a.zi).compare(b.zi)<0;//两个字符串进行比较,字典序小的排在前面
}
int main()
{int t,n,i,j,k,p;string s,s1;scanf("%d",&t);while(t--){p=0;E f[100010];cin>>s;f[p].zi=s;f[p].b=0;n=s.size();for(i=1;i<=n;i++){string s1;for(j=i;j<n;j++){s1+=s[j];}for(k=0;k<i;k++){s1=s1+s[k];//获取移动的字符串}p++;f[p].zi=s1;f[p].b=i;}sort(f,f+p,cmp);//根据字典序来排序cout<<f[0].b<<endl;}return 0;
}#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
int main()
{int t,n,i,k;string s,s1,s3;scanf("%d",&t);while(t--){cin>>s;s3=s;k=0;n=s.size();for(i=1;i<=n;i++){string s1,s2;s1=s.substr(i,n-i);s2=s.substr(0,i);s1=s1+s2;if(s3.compare(s1)>0)//此函数用来比较字典序{s3=s1;k=i;}}printf("%d\n",k);}return 0;
}#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
map<string,int>a;
int main()
{int t,n,i;string s,s1;scanf("%d",&t);while(t--){a.clear();cin>>s;a[s]=0;n=s.size();for(i=1;i<=n;i++){string s1,s2;s1=s.substr(i,n-i);s2=s.substr(0,i);//获取字符串从0开始取i个s1=s1+s2;if(a[s1]==0)a[s1]=i;}map<string,int>::iterator it=a.begin();//map<string,int>是按照最小字典序来排列的cout<<it->second<<endl;}return 0;
}#include<stdio.h>
#include<string.h>
#define maxn 100010
int less(char s[],int p,int q)
{int n=strlen(s);int i;for(i=0;i<n;i++){if(s[(p+i)%n]!=s[(q+i)%n])return s[(p+i)%n]<s[(q+i)%n];}return 0;
}
int main()
{int t,ans,n,i;char s[maxn];scanf("%d",&t);while(t--){scanf("%s",s);ans=0;n=strlen(s);for(i=1;i<n;i++){if(less(s,i,ans))ans=i;}printf("%d\n",ans);}return 0;
}
