【题目来源】
【题目描述】
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫 Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 i+1 个方块。如果全都一样，那么这两个工艺品就一样漂亮。
【输入格式】
第一行一个整数 n，代表方块的数目。
第二行 n 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值，保证其小于 30。
【输出格式】
一行 n 个整数，代表最美观工艺品从左到右瑕疵度的值。
【输入样例】
10
10 9 8 7 6 5 4 3 2 1
【输出样例】
1 10 9 8 7 6 5 4 3 2
【数据范围】
对于 20% 的数据，n≤1000；
对于 40% 的数据，n≤10^4；
对于 100% 的数据，n≤3×10^5。
【算法分析】
● 本题是寻找字符串（或序列）最小表示的经典问题。
● 算法原理：利用数组倍增处理环形结构，或称之为解环成链，即将环形结构转为其 2 倍长度的线性结构。通过 while 循环进行双指针比较，i 和 j 分别代表当前竞争最小起始点的两个候选下标。当发现失配时，根据大小关系利用性质 i+=k+1 或 j+=k+1 快速跳过不可能成为答案的区间，从而实现线性扫描。最终输出从 min(i, j) 开始的 n 个元素。
【算法代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=6e5+5;
int a[maxn];
int n;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=0; i<n; i++) {cin>>a[i];a[i+n]=a[i]; //auxiliary sequence of length 2n}int i=0,j=1; //Two starting positionsint k=0; //Indicates the offsetwhile(i<n && j<n && k<n) {if(a[i+k]==a[j+k]) k++;else {if(a[i+k]>a[j+k]) i+=k+1;else j+=k+1;if(i==j) i++;k=0;}}int p=min(i,j);for(int q=0; q<n; q++) {cout<<a[p+q]<<" ";}return 0;
}/*
in:
10
10 9 8 7 6 5 4 3 2 1out:
1 10 9 8 7 6 5 4 3 2
*/
【参考文献】