|
问题描述
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。
输入格式
第一行两个整数n，代表方块的数目。
第二行n个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。
输出格式
一行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<=10000
对于100%的数据，n<=300000
【分析】
根据题意，我们使前面的数尽可能的小，于是第一位就应该是最小的一位。由于我们是处理同一个字符串，所以当第一位一开始就是最小一位时，就是最漂亮的。所以只需处理原字符串的最小表示即可。
由于输入中有空格，所以我选用数组代替字符串。
【标程】
1 #include<iostream> 2 #define maxn 300003 3 using namespace std; 4 int Len, i, j, k; 5 int S[maxn * 2]; 6 void ini() { 7 scanf("%d", &Len); 8 for (int q = 0; q < Len; ++ q)scanf("%d", &S[q]), S[q + Len] = S[q]; 9 i = 0; 10 j = 1; 11 } 12 int Ex_() { 13 while (i < Len && j < Len) { 14 for (k = 0; k < Len; ++ k) 15 if (S[i + k] != S[j + k])break; 16 if (k == Len)break; 17 if (S[i + k] > S[j + k])i += k + 1; 18 else if (S[i + k] < S[j + k])j += k + 1; 19 if (i == j)++ j; 20 } 21 return min(i, j); // 返回最小的一位的位置 22 } 23 void solve() { 24 int St = Ex_(); 25 printf("%d ", S[St]); //最关键的两步，由于最小表示法的方法是环形操作，最后一位又会回到第一位，所以先输出第一位，后面for循环结束条件就巧妙的设为i！=St，解决死循环。 26 for (int i = St + 1; i != St; i = (i + 1) % Len)printf("%d ", S[i]); // 取模很关键 27 } 28 int main() { 29 ini(); 30 solve(); 31 return 0; 32 }