[蓝桥杯 2018 国 C] 交换次数
题目描述
IT 产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯（简称 BAT）在某海滩进行招聘活动。
招聘部门一字排开。由于是自由抢占席位，三大公司的席位随机交错在一起，形如：
ABABTATT，这使得应聘者十分别扭。
于是，管理部门要求招聘方进行必要的交换位置，使得每个集团的席位都挨在一起。即最后形如：
BBAAATTT 这样的形状，当然，也可能是：
AAABBTTT 等。
现在，假设每次只能交换 2 2 2 个席位，并且知道现在的席位分布，
你的任务是计算：要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。
输入格式
输入是一行
n
n
n 个字符（只含有字母 B、A 或 T），表示现在的席位分布。
输出格式
输出是一个整数，表示至少交换次数。
样例 #1
样例输入 #1
TABTABBTTTT
样例输出 #1
3
样例 #2
样例输入 #2
TTAAABB
样例输出 #2
0
提示
输入字符串的长度 n n n 不大于 1 0 5 10^5 105。
时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛
思路
从输入中读取席位分布，然后用一个 map 记录 A、B、T 的数量。定义了一个变量 ans，用来存储最小的交换次数，初始化为一个很大的数。然后定义了一个字符串 abt，是 A、B、T 的一个排列，然后使用 do while 循环，对 abt 进行全排列，调用 calc 函数计算需要交换的最小次数。
然后定义一个 calc 函数，该函数接受一个字符串，该字符串是 A、B、T 的一个排列，然后计算如果席位按照该排列进行排列，需要交换的最小次数。
在 calc 函数中，首先定义了两个变量 s01 和 s02，这两个变量用来记录0区的字符需要移动到1区和2区的数量。然后遍历字符串的前 cnt[code[0]] 个字符，如果字符是 code[1]，则 s01 加一，如果字符是 code[2]，则 s02 加一。这个过程就是计算0区的字符需要移动的数量。
然后定义了两个变量 s20 和 s21，这两个变量用来记录2区的字符需要移动到0区和1区的数量。然后遍历字符串的后 cnt[code[2]] 个字符，如果字符是 code[0]，则 s20 加一，如果字符是 code[1]，则 s21 加一。这个过程就是计算2区的字符需要移动的数量。
当0区和1区都完成排序后，2区自然也就排序完成了。不需要再检查2区。
s01 和 s21 分别表示0区需要移到1区和2区需要移到1区的字符数量，这两部分的字符移动是必须的。至于 s02 和 s20，表示0区需要移到2区和2区需要移到0区的字符数量，这两部分的字符移动存在冲突，即如果0区的字符移到2区，那么2区的字符就不能移到0区，反之亦然。因此，选择 s02 和 s20 中的最大值，即选择需要移动的字符数量最多的区域进行移动。这样可以保证总的交换次数最少。
所以最少的交换次数等于0区需要移到1区的字符数量，加上2区需要移到1区的字符数量，再加上0区和2区中需要移动的字符数量最多的那个区域的字符数量。函数返回 sum = s01 + s21 + max(s02, s20); 。
对每一个排列，计算需要交换的最小次数，然后更新 ans。最后，输出 ans。
AC代码
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
int n;
string s;
int len = s.length();
map<char, int> cnt;
/*
将字符串划分为0、1、2三个区域
每个区域排序后应该只有一种字符
*/
ll calc(string code) {
ll sum = 0;
ll s01 = 0;
ll s02 = 0;
// 检查0区
for (int i = 0; i < cnt[code[0]]; i++) {
// cout << s[i] << endl;
if (s[i] == code[1]) {
// 该字符属于1区，将其字符从0区移到1区
s01++;
} else if (s[i] == code[2]) {
// 该字符属于2区，将其从0区移到2区
s02++;
}
}
ll s20 = 0;
ll s21 = 0;
// 检查2区
for (int i = s.length() - 1; i >= s.length() - cnt[code[2]]; i--) {
// cout << s[i] << endl;
if (s[i] == code[1]) {
// 该字符属于1区，将该字符从2区移到1区
s21++;
} else if (s[i] == code[0]) {
// 该字符属于0区，将该字符从2区移到0区
s20++;
}
}
sum = s01 + s21 + max(s02, s20);
// cout << sum << endl;
return sum;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> s;
for (const auto i : s) {
cnt[i]++;
}
ll ans = INF;
string abt = "ABT";
do {
ans = min(ans, calc(abt));
} while (next_permutation(abt.begin(), abt.end()));
cout << ans << "\n";
return 0;
}