积木游戏

题目描述

小云和小吉在玩积木游戏，他们手上有很多积木，每个积木上面都有一个字母。

现在他们把所有的积木都排在一条队列上，队列有一个完美值，这个完美值就是积木队列上的字母组成的字符串的字典序，字典序越大完美值就越大。

小云和小吉轮流玩游戏，每次游戏，玩家要把积木队列的第一个积木取出来，并把它放到积木队列的最后一个位置。

这个游戏看起来很简单，小云和小吉想知道这个游戏一直玩下去，所能得到的积木队列的最大完美值是多少？

输入输出格式

输入格式：

输入2行，第一行一个数n，表示积木数量
第二行一个长度为n的字符串，表示积木队列的初始状态

输出格式：

输出一行，最大完美值的积木队列

输入输出样例

输入样例：

11
abcdefghijk

输出样例：

kabcdefghij

提示信息

数据范围：
对于 20%的数据，n≤1000；
对于 40%的数据，n≤10^4；
对于 100%的数据，n≤3×10^5。

解法

#include <bits/stdc++.h>
using namespace std;
int n,i,j=1,k;
string s;
int main() {
	cin >>n >>s;
	while (i<n && j<n) {
		while (k<n && s[(i+k)%n]==s[(j+k)%n]) k++;
		if (k==n) break;
		if (s[(i+k)%n]<s[(j+k)%n])
			i=i+k+1;
		else
			j=j+k+1;
		if (i==j) i++;
		k=0;
	}
	k=min(i,j);
	cout <<s.substr(k,n) <<s.substr(0,k);
	return 0;
}