codeforces C. Largest Subsequence

思路

• 首先是要选出 $LargestSubsequence$ ，第一个字符是整个串最大的，第二个是第一个的位置后面最大的 $\dots$ ，我用的是优先队列第一关键字大小，第二关键字位置。（其实不用这样，用栈就行，我复杂了）
• 然后你会发现其 $cyclic$ 次数是字符串长度减 $1$ ，过程就是交换首位字符的位置，向中心扩展。
• 有可能你选出来的字符串从第一个开始有连续一样的，如：$zzzdc$ ，$zzz$ 就是连续一样的，试想如果是这样还是需要字符串长度减 $1$ 次？当然不是，而是长度减去连续的长度。
• 最后结束检查一遍是否 $sorted$

Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x) {
    if (x < 0) x = -x, put(45);
    if (x > 9) write(x / 10);
    put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 1e5 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
struct p {
    char s;
    int pos;
    il bool operator <(const p & b) const {
        return s < b.s || (s == b.s && pos > b.pos);
    }
};
signed main() {
    int T = read();
    while (T--) {
        int n = read();
        priority_queue<p> q;
        string s;
        cin >> s;
        bool f2 = 1;
        for (int i = 0; i < s.size(); ++i) q.push({s[i], i});
        vector<p> a;
        while (!q.empty()) {
            a.push_back(q.top());
            int pos = q.top().pos; q.pop();
            while (!q.empty() && q.top().pos < pos) q.pop();
        }
        int l = 0, r = a.size() - 1, cnt = a.size() >> 1;
        int cnt1 = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i].s == a[0].s) ++cnt1;
        }
        while (cnt--) swap(s[a[l++].pos], s[a[r--].pos]);
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] < s[i - 1]) {f2 = 0; break;}
        }
        f2? (write(a.size() - cnt1), put(10)): puts("-1");
    }
    return 0;
}