最小循环重构

链接：https://ac.nowcoder.com/acm/contest/831/D
来源：牛客网

Rabbit得到了一个字符串，她的好朋友xxx可以给这个字符串施加一次魔法。魔法可以选择字符串的任一位置，并将该位置后面的所有字符水平拼接到串首。

例如：对于字符串abcde，可以通过施加魔法得到cdeab。

如果xxx通过施加魔法将字符串的字典序变得严格比之前的小，那么他将拿走这一字符串。Rabbit想知道自己的字符串会不会被xxx拿走。

5
cdeab

YES

xxx可以把e之后的部分“ab”放到串首，得到abcde，字典序比cdeab小，故将拿走字符串。

思路

是否存在一种拼接方式, 将某一个位置到结尾的串放到开头, 得到的新串比原来的字典序小。

因为每次都是接到开头, 那么可以不可以这么看： 将字符串首尾相接为环, 找一个位置放开头的操作 可以转化为选择一个位置开始枚举n次。

也就是循环重构, 那我们这题就是求最小字典序的循环重构串。

1

用i来枚举当前最小串的起点, j来枚举新串的起点, 用k来做偏移量 s[i + k], s[j + k] 判断两个串谁的字典序小。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
bool flag =  true;
int n;
string s;
 
int getmin(string s)
{
    int i = 0, j = 1;
    while(i < n && j < n)
    {
        int k = 0;
        while(k < n && s[i + k] == s[j + k]) k++;
        if(k == n) break;
        if(s[i + k] > s[j + k]) i += k + 1 + (i==j);
        else j += k + 1 + (i==j);
    }
    return min(i,j);
}
 
int main()
{
    cin >> n;
    cin >> s;
    s += s;
    if(!getmin(s)) cout << "NO\n";
    else cout << "YES\n";
    return 0;
}