【洛谷】P1368 【模板】最小表示法

https://www.luogu.com.cn/problem/P1368

题目描述：
小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏，叫Minecraft。他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。两个工艺品美观的比较方法是，从头开始比较，如果第 i i i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 i + 1 i+1 i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。

输入格式：
第一行一个整数 n n n，代表方块的数目。
第二行 n n n个整数，每个整数按从左到右的顺序输出方块瑕疵度的值。

输出格式：
一行 n n n个整数，代表最美观工艺品从左到右瑕疵度的值。

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

其实就是求循环同构的字典序最小的表示，即最小表示法，参考https://blog.csdn.net/qq_46105170/article/details/125243122。代码如下：

#include 
#include 
using namespace std;

// 长度要开两倍
const int N = 6e5 + 10;
int n;
int a[N];

int get() {
  int i = 0, j = 1, k;
  while (i < n && j < n) {
    k = 0;
    while (i + k < n && j + k < n && a[i + k] == a[j + k]) k++;
    if (k == n) break;
    a[i + k] > a[j + k] ? i += k + 1 : j += k + 1;
    if (i == j) j++;
  }

  return min(i, j);
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  memcpy(a + n, a, (n - 1) * sizeof(int));
  int idx = get();
  for (int i = idx; i < idx + n; i++) printf("%d ", a[i]);
}

时空复杂度 O ( n ) O(n) O(n)。