2123. [HZOI 2015] Glass Beads

★★★   输入文件：MinRepresentations.in   输出文件：MinRepresentations.out   简单对比

时间限制：1 s   内存限制：1024 MB

【题目描述】

给定长度为n（n<=300000）的循环同构的字符串，定义最小表示为该字符串的字典序最小的同构表示，请输出这个表示。

【输入格式】

第一行是串的长度，第二行是字符串。

【输出格式】

串的最小表示。

【样例输入】

 

10

helloworld

 

【样例输出】

dhelloworl

【题目来源】

HZOI2015 改编自poj1509

#include
     
      #include
      
       #include
       
        #define maxn 300010using namespace std;int n;char s[maxn];int getmn(){    int i=0,j=1,k=0;    while(i
        
         
          
           0)i+=k+1; else j+=k+1; if(i==j)j++; k=0; } } return min(i,j);}int main(){ freopen("MinRepresentations.in","r",stdin);freopen("MinRepresentations.out","w",stdout); scanf("%d%s",&n,s); int ans=getmn(); for(int i=1,j=ans;i<=n;i++,j++){ printf("%c",s[j%n]); } return 0;}