【题解】P1368【【模板】最小表示法】

_l_l_ · 2020-10-04 09:00:24 · 题解

最小表示法

给定一个字符串(或数组)，可以将字符串末尾字母移动到最前面，也可以将首位字母移动到最前面，问移动若干次后，字典序最小的字符串？

我们可以使用双指针的做法，下面讲解一下双指针做法的过程与正确性：

1. seq[i]不等于seq[j]

   不妨设seq[i] < seq[j]

   由于seq[j]太大了，因此我们保留seq[i]，将j加1

2. seq[i]等于seq[j]

   假设从seq[i]与seq[j]开始，连续k个数都相等，第k+1个数不相等，那么：

   不妨设seq[(i + k) % n] < seq[(j + k) % n]

   因此以j, (j + 1) % n, ..., (j + k) % n开头的"答案"均可被i, (i + 1) % n, ..., (i + k) % n省略掉，可以将j加上k + 1

仔细观察发现第一种分类可以归为第二种分类k=0时的情况 因此，理论上来讲，这其实是一个三指针做法好吧我瞎编的

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 300001;
int seq[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &seq[i]);
    }
    int i, j, k;
    for (i = 0, j = 1, k = 0; i < n && j < n && k < n; ) {
        if (seq[(i + k) % n] == seq[(j + k) % n]) {
            k++;
        }
        else {
            seq[(i + k) % n] > seq[(j + k) % n] ? i += k + 1 : j += k + 1;
            if (i == j) i++;
            k = 0;
        }
    }
    int ans = min(i, j);
    for (k = 0; k < n; k++) {
        printf("%d ", seq[(ans + k) % n]);
    }
    return 0;
}