题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，只包含小写英文字母。

每次操作，选出$s$中的字典序最大的子序列，将其循环右移一位。例如$s=$zbca 选出子序列zca，循环右移一位后变成azc，此时$s$变成abzc。

使$s$变成非递减，至少要操作多少次？如果无法做到，输出$-1$。

输入样例

6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz

输出样例

0
1
-1
2
6
0

算法

贪心

这种要思考、打草稿的题目一般都能卡我好久。想了很久其实没想到特别好的方案，只能明确第一次要操作的子序列应该是一个以$s$中最大字母$mx$起头的最长单调不增序列，假设这个序列的长度为$len$，那么就要向右移动$len-cnt$次，其中$cnt$是序列中$mx$的出现次数，将整个序列变为单调不减的。不是很确定这里如果右移次数小于$len-cnt$会不会有什么新情况得到更好的解，或是让无解变有解，但是造了几个小$case$发现最终都会让右移次数补到$len-cnt$，少移几次没什么意义。

然后发现一个很重要的事实：再选字典序最大的子序列肯定也会选到$mx$开头的序列。但经过第一次子序列选择之后，所有$mx$都应该被排到了最后，这样就没有操作空间了，怎么选都是选出一段$mx$的后缀。所以只有一次选择子序列的操作，选出来之后把最大的字母右移到尾部。如果此时$s$有序了那就可以做到，打印移动次数$len-1$；否则就做不到让$s$有序，直接打印$-1$。

接下来关键就在于如何构建第一个最长非增子序列？先遍历$s$获得一个映射$mp$“字母$\rightarrow$索引列表”，将所有$mx$的索引加入到一个数组$pos$中，然后降序遍历比$mx$小的字母$c$，只要$c$存在大于$pos.back()$的索引（二分查找判断），就把后面所有的$c$索引加入到$pos$数组中。通过这种方式得到$pos$之后，跑一遍相对双指针，把索引$pos$对应的子序列变为单调不减即可。

复杂度分析

时间复杂度

预处理出$mp$的时间复杂度为$O(nlog_2\Sigma)$，$\Sigma$是字符集大小，本题中$\Sigma=26$。然后获得字典序最大的最长非增子序列的索引，在最差情况下要遍历字符集，并且每个字符的索引列表需要做一次二分查找，由于所有字母的索引列表加起来就是$O(n)$规模的，因此二分查找的时间复杂度为$O(log_2n)$。但是获得的序列可能是$O(n)$级别的长度，所以这个过程的时间复杂度还是$O(n)$，接下来双指针算法的时间复杂度也是$O(n)$。

综上，整个算法的时间复杂度为$O(nlog_2\Sigma)$，可以看成是一个常数比较大的线性算法。

空间复杂度

除了输入的字符串，空间消耗就是有序映射表$mp$，它其中会存储$O(n)$级别的下标，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n;
char s[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        if(is_sorted(s + 1, s + n + 1)) {
            puts("0");
        }else {
            map<char, vector<int>> mp;
            for(int i = 1; i <= n; i++) {
                mp[s[i]].push_back(i);
            }
            vector<int> pos;
            char mx = mp.rbegin()->first;
            for(int x: mp[mx]) {
                pos.push_back(x);
            }
            int mxcnt = pos.size();
            mp.erase(mx);
            for(char c = mx - 1; c >= 'a'; c--) {
                if(mp.count(c)) {
                    auto& v = mp[c];
                    int j = upper_bound(v.begin(), v.end(), pos.back()) - v.begin();
                    int del = v.size() - j;
                    while(j < v.size()) {
                        pos.push_back(v[j++]);
                    }
                    while(del--) {
                        v.pop_back();
                    }
                    if(v.empty()) mp.erase(c);
                }
            }
            int l = 0, r = pos.size() - 1, ans = pos.size() - mxcnt;
            while(l < r) {
                swap(s[pos[l]], s[pos[r]]);
                l++, r--;
            }
            printf("%d\n", is_sorted(s + 1, s + n + 1)? ans: -1);
        }
    }
    return 0;
}