Codeforces Round #723 (Div. 2) D. Kill Anton

D. Kill Anton

題意

給出一個隻有 4 4 4 個字母組成的字元串 S S S，請對這個字元串重新排列得到字元串 T T T，使得對字元串 T T T 需要做最多次變換得到字元串 S S S 。每次變換可以交換相鄰的兩個字母。

題解

• 從 T T T 到 S S S 的變換過程，一定不會交換相鄰相同的字母；
• 從 T T T 到 S S S 的變換次數等于從 S S S 到 T T T 的變換次數；
• T T T 一定是相同的字母連續出現，一共有 4 4 4 種字母，是以一共有 4 ! = 24 4!=24 4!=24 種可能的答案，選出變換次數最多的即可。
• 變換次數等于逆序對個數。

代碼

#include<bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
char s[maxn], t[maxn], ans[maxn];
map<char, int> mp;
ll n, c[10], dis;
void add(int pos, int x) {
    while (pos < 10) c[pos] += x, pos += pos & -pos;
}
ll getsum(int pos) {
    ll ans = 0;
    while (pos) ans += c[pos], pos -= pos & -pos;
    return ans;
}
bool check() {
    ll d = 0;
    memset(c, 0, sizeof(c));
    rep(i, 1, n) {
        d += i - 1 - getsum(mp[s[i]]);
        add(mp[s[i]], 1);
    }
    if (d < dis) return 0; 
    dis = d;
    return 1;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        dis = 0;
        vector<int> cnt(26);
        rep(i, 1, n) cnt[s[i] - 'A']++;
        char D[5] = "ANOT";
        do {
            int m = 0;
            for (int i = 0; i < 4; ++i) {
                mp[D[i]] = i + 1;
                rep(_, 1, cnt[D[i] - 'A']) t[++m] = D[i];
            }
            if (check()) rep(i, 1, n) ans[i] = t[i];
        } while (next_permutation(D, D + 4));
        ans[n + 1] = 0;
        printf("%s\n", ans + 1);
    }
    return 0;
}