題目

尋找字串 s 的某個排列 t，使得 s 經過相鄰字母交換變成 t 時交換次數最大。

解法

考慮只有兩種字母的情況:

$$s=\texttt{yyyxyyy}$$，x 移到最後或最前即可。

$$s=\texttt{yyxyyxyy}$$，沒必要把兩個 x 移到中間，因為之後可以把他們往左(或右)移動，貢獻值不會更差，必有一個在最左或最右。

1
2

      x    x
|—————|————|——|

假設左邊長度較大，不管中間長度為何，一定一起移到左邊，反之亦然。
$$s=\texttt{yyxyxyxyy}$$ 也可套用同樣概念，相同字母一定在一起。

在多種字母情況，對字母 x 來說，其他字母都是 “別人”，x 一起到最左或右。
對每種字母使用相同概念，雖然不知道他們的順序，但相同字母一定擠在一起。

題目中字串只有四種字母，只要 $$O(4!n)$$ 枚舉他們的排列然後計算最大貢獻就好。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void solve() {
    string s, t = "ANOT", result;
    cin >> s;
    ll dict[4], max_swap = -1, n_swap;
    do {
        fill_n(dict, 4, 0);
        n_swap = 0;
        for(char c : s) {
            n_swap += accumulate(dict + t.find(c) + 1, dict + 4, 0ll);
            dict[t.find(c)]++;
        }
        if(n_swap > max_swap) {
            max_swap = n_swap;
            result = t;
        }
    } while(next_permutation(all(t)));
    fill_n(dict, 4, 0);
    for(char c : s) {
        dict[result.find(c)]++;
    }
    for(int i = 0; i < 4; i++) {
        cout << string(dict[i], result[i]);
    }
    cout << '\n';
}

參考資料

https://blog.csdn.net/xin_jun/article/details/117393947 https://blog.csdn.net/qq_51945248/article/details/117567898 https://zh.xloypaypa.pub/codeforces-round-723-kill-anton-ti-jie-java-c/