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

题目链接：D. Kill Anton
转载自：https://www.cnblogs.com/violentbear/p/14836564.html
不得不说官方题解证明没个例子半个下午一直看不懂！！！
下次看不懂要去用题目搜题解orz

思路：
先考虑他会怎么做才能最少次数还原串。

我们发现对于一个串$b$若将它还原成串$a$，最好是每一次交换，都减少一个逆序对数量，这里的逆序对数量是以$a$为中心来说的。
这显然是最优解，因为当$b$相对于$a$的逆序对数量减为$0$时，$b=a$。而且他的交换方式是相邻两个字符间进行交换，所以每一次交换最多减少一个逆序对数量。

那我们考虑如何才能产生最多的逆序对的数量，首先我们先看一下只有两个字符的情况：

$(A1)NNNN(A2)NN(A3)N$

为了方便，将$A$每一个都标上了序号，我们发现$A1$一直移动到$A2$的位置，都在不断地产生逆序对，如果$A1$再向后移动，那么当前移动的就不是$A1$了，那我们可以看成是$A2$移动，$A1$停在原来$A2$的位置，那么显然，$A1$停在原来$A2$的位置就绝对不是最优解，只有$A1，A2，A3$都移动到最后面，才产生最大的逆序对数，所以我们发现，最优解构造有一种情况一定是把相同字符都放在一起，所以我们的做法就很好做了，这里我们只考虑两个字符，因为在考虑两个字符时，即使插入任意别的字符在任意的位置，也对于当前字符排列的逆序对没有什么影响。然后我们暴力枚举字符对，算出每一种字符对的贡献，最后利用全排列函数来求解最优解。
$Code:$

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
#endif
using ll = int64_t;void solve(){
    string c = "ANOT";string s;cin >> s;ll best = -1;string bests = "";do {
    string cur = s;string res = "";ll score = 0;for(char l : c){
    string z = "";int f = 0;for(char x : cur){
    if(x == l){
    score += f;res += x;} else {
    f++;z += x;}}cur = z;cout<<cur<<'\n';cout<<res<<'\n'<<'\n';}cout<<res<<' '<<score<<'\n';if(score > best){
    best = score;bests = res;}} while (next_permutation(c.begin(), c.end()));cout << bests << '\n'<<'\n';
}int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);int T;cin >> T;while(T--) solve();
}