2123. [HZOI 2015] Glass Beads

★★★ 输入文件：MinRepresentations.in 输出文件：MinRepresentations.out 简单对比
时间限制：1 s 内存限制：1024 MB

【题目描述】

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

【输入格式】

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

【输出格式】

串的最小表示。

【样例输入】

helloworld

【样例输出】

dhelloworl

【题目来源】

HZOI2015 改编自poj1509

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 300010

using namespace std;

int n;

char s[maxn];

int getmn(){

    int i=,j=,k=;

    while(i<n&&j<n&&k<n){

        int 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 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=,j=ans;i<=n;i++,j++){

        printf("%c",s[j%n]);

    }

    return ;

}

巴特西

cogs 2123. [HZOI 2015] Glass Beads