洛谷P2870 [USACO07DEC] Best Cow Line G 题解

题意：

Farmer John 打算带领 $N$（$1 \leq N \leq 5 \times 10^5$）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。

今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。

FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。

他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。

现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。

输入格式：

第一行一个整数 $N$。

接下来 $N$ 行每行一个大写字母，表示初始队列。

输出格式：

输出一个长度为 $N$ 的字符串，表示可能的最小字典序队列。

每输出 $80$ 个字母需要一个换行。

考虑贪心。如果两端不相同，就取较小的那个。

如果两端相同，就比较里面那个，比如 $\tt ACSBBA$ 就去后面那个。

如果里面那个也相同呢？比如 $\tt CAEAAC$ ，如果还按照刚才的取就会得到 $\tt CACAAE$ ，而正解是 $\tt{CAACAE}$ 。

因此我们需要一直比较直到两个不相同，我们可以二分这个长度，然后用字符串哈希比较两个串。

时间复杂度 $\mathcal{O}(n \log n)$ ，代码不贴了。

下面再来讲讲后缀数组（SA）的做法。设 $f_i$ 为第 $i$ 个后缀，$g_i$ 为第 $i$ 个前缀。

因为取两端字符的时候通常是用两个指针 $l,r$ 维护，所以下面定义 $s_l,s_r$ 为当前的两端。

如果 $s_l=s_r$ ，我们直接比较 $f_l$ 和 $g_{r}$ ，取较小的那一端（其实就是上面的那个贪心）

按照套路，我们可以构造一个原串 + 0 + 反串的串，然后跑后缀排序。

比如 $\tt{AABCAA}$ 可以构造 $\mathtt{AABCAA}\,0\,\mathtt{AACBAA}$ （中间是零）。~~不过本题其实不需要这么构造~~

时间复杂度 $\mathcal{O}(n \log n)$ ，肯定比字符串哈希慢点。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N], ans[N];
int sa[N], rk[N * 2], tmp[N * 2], cnt[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void init(const int n)
{
    const int m = max(n, 333);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= n; i++) s[2 * n + 1 - i + 1] = s[i];
    init(2 * n + 1); int l = 1, r = n, t = 0;
    while(l < r)
    {
        if(s[l] < s[r]) ans[++t] = s[l++];
        else if(s[l] > s[r]) ans[++t] = s[r--];
        else {
            if(rk[l] < rk[2 * n + 1 - r + 1]) ans[++t] = s[l++];
            else ans[++t] = s[r--];
        }
    }
    ans[++t] = s[l];
    for(int i = 1; i <= n; i++) { cout << ans[i]; if(i % 80 == 0) cout << '\n'; }
    return 0;
}