最小表示法模板题-526互联

模板题

/*
循环结构的最小字典序问题
最小表示发模板题
利用前面已经比较过的信息，从而pass掉某些答案，实现o1的查找
如果全部相同，那么一次查找就可以了
反之会进行跳转，跳到那个较小的地方
*/
#include <bits/stdc++.h>
using namespace std;
const int M=6e5+5;

int a[M];

int solve(int n) {
    int i=1,j=2,k=0;
    while(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)j++;
            k=0;
        }
    }
    return min(i,j);
}

int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
    int p=solve(n);
    for(int i=p;i<p+n;i++)cout<<a[i]<<' ';
    return 0;
}

表示法

模板