题目给出一个字符串，由a~z表示甜度，随字典序增大，字符串首尾相连形成一个圈，要求从一个位置开始字典序最大的字符串，输出位置以及是顺时针还是逆时针表示。顺时针用0表示，逆时针用1表示。
此题只需要查找字符串的最大字典序排列即可，模拟对字符串的翻转以及排列操作，可以用二分来查找位置来节省时间。
最小表示法模板：
int getmin(char *s){
int n=strlen(s);
int i=,j=,k=,t;
while(i<n && j<n && k<n){
t=s[(i+k)%n]-s[(j+k)%n];
if (!t) k++;
else{
if (t<) i+=k+;
else j+=k+;
if (i==j) j++;
k=;
}
}
return i<j?i:j;
}
将t<0改为t>0即可求最大字典序。
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std; char input[],s[];
int t,len; int getmin(char *s){
int n=strlen(s);
int i=,j=,k=,t;
while(i<n && j<n && k<n){
t=s[(i+k)%n]-s[(j+k)%n];
if (!t) k++;
else{
if (t<) i+=k+;
else j+=k+;
if (i==j) j++;
k=;
}
}
return i<j?i:j;
} int judge(int mid){
int pos;
for(int i=;i<len;i++)
s[i]=input[(mid+i)%len];
pos=getmin(s);
if(pos>len--mid) return ;///
else return ;
} int main(){
while(~scanf("%d",&t)){
while(t--){
scanf("%d%s",&len,input);
char s1[],s2[];
int start=getmin(input);
for(int i=;i<len;i++)
s1[i]=input[(start+i)%len];///从最小起点重构字符串
reverse(input,input+len);///翻转字符串
int start1=getmin(input);
for(int i=;i<len;i++)
s2[i]=input[(start1+i)%len];///从最小起点重构字符串
if(strcmp(s1,s2)>)
{printf("%d 0\n",start+);continue;}
int l=start1,r=len-,mid;
while(l<=r){
mid=(l+r)/;
if(judge(mid))
l=mid+;
else
r=mid-;
}
start1=r;
for(int i=;i<len;i++){
s2[i]=input[(start1+i)%len];
}
if(strcmp(s1,s2)<){
printf("%d 1\n",len-start1);continue;
}
else if(start<=len-start1){
printf("%d 0\n",start+);
}
else printf("%d 1\n",len-start1);
}
}
return ;
}