「BZOJ 2882」工艺

题目大意：给出一个长度为 $n$ 的字符串 $s$，求一个与其循环同构的字典序最小的字符串。$n \leq 3 \times 10^5$

#include <cstdio>
#define min(x, y) x < y ? x : y

int n, a[300005];

int exp() {
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        int t = a[(i+k)%n] - a[(j+k)%n];
        if (!t) ++k;
        else {
            if (t > 0) i += k + 1;
            else j += k + 1;
            if (i == j) ++j;
            k = 0;
        }
    }
    return min(i, j);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int t = exp();
    for (int i = 0; i < n; ++i)
        printf("%d ", a[(t+i)%n]);
    return 0;
}

时间复杂度 $O(n)$