A40805. 交换次数
填空题
困难
知识点
题目描述
交换次数
题目描述
IT产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯（简称BAT）在某海滩进行招聘活动。
招聘部门一字排开。由于是自由抢占席位，三大公司的席位随机交错在一起，形如：
ABABTATT，这使得应聘者十分别扭。
于是，管理部门要求招聘方进行必要的交换位置，使得每个集团的席位都挨在一起。即最后形如：
BBAAATTT 这样的形状，当然，也可能是：
AAABBTTT 等。
现在，假设每次只能交换2个席位，并且知道现在的席位分布，
你的任务是计算：要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。
输入是一行n个字符（只含有字母B、A或T），表示现在的席位分布。
输出是一个整数，表示至少交换次数。
比如，输入：
TABTABBTTTT
程序应该输出：
3
再比如，输入：
TTAAABB
程序应该输出：
0
我们约定，输入字符串的长度n 不大于10万
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
参考答案
const int INF = 0x3f3f3f3f;
string s;
char t[][4] = {"BAT", "BTA", "ABT", "ATB", "TBA", "TAB"};
int f(char A, char B, char C) {
int a = 0, b = 0, c = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == A)
a++;
else if (s[i] == B)
b++;
else
c++;
}
int cia = 0, cib = 0, cic = 0, ci = 0;
for (int i = 0; i < a; i++) {
if (s[i] != A)
ci++;
if (s[i] == B)
cib++;
}
for (int i = a; i < b + a; i++) {
if (s[i] == A)
cia++;
if (s[i] == C)
cic++;
}
ci += cic + cia - min(cib, cia);
return ci;
}
void solve() {
cin >> s;
int Min = INF;
for (int i = 0; i < 6; ++i)
Min = min(Min, f(t[i][0], t[i][1], t[i][2]));
cout << Min;
}
上一题
下一题