[蓝桥杯]交换次数

交换次数

题目描述

IT 产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯（简称 BAT ）在某海滩进行招聘活动。

招聘部门一字排开。由于是自由抢占席位，三大公司的席位随机交错在一起，形如：BABTATT，这使得应聘者十分别扭。

于是，管理部门要求招聘方进行必要的交换位置，使得每个集团的席位都挨在一起。即最后形如：BBAAATTT 这样的形状，当然，也可能是：AAABBTTT 等。

现在，假设每次只能交换 2 个席位，并且知道现在的席位分布，你的任务是计算：要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。

输入描述

输入是一行 nn 个字符（只含有字母 B、A 或 T ），表示现在的席位分布。

输出描述

输出是一个整数，表示至少交换次数。

输入输出样例

示例

输入

TABTABBTTTT

输出

3

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 573  |  总提交次数: 720  |  通过率: 79.6%

难度: 中等   标签: 2018, 暴力, 国赛

方法思路

题目要求将字符串中的字母B、A、T分别分组，每组字母连续出现，计算最少交换次数。交换操作每次可以交换任意两个位置的字符。核心思路是枚举所有可能的分组顺序（共6种：BAT、BTA、ABT、ATB、TBA、TAB），对每种顺序计算将原字符串调整为该顺序所需的最小交换次数，然后取所有顺序中的最小值。

解决步骤

1. 枚举分组顺序：遍历6种可能的分组顺序（BAT、BTA、ABT、ATB、TBA、TAB）。

2. 统计字母数量：计算字符串中B、A、T的数量。

3. 定义分组边界：根据当前分组顺序，将字符串分为三段，每段对应一个字母。

4. 统计错误位置：遍历每段，统计错误字母（即不属于本段的字母）的数量。

5. 计算交换次数：

   • 直接交换：交换两个错误字母，使它们同时归位（例如，将A段中的B与B段中的A交换）。直接交换次数为各段中可配对错误字母数量的最小值之和。

   • 循环交换：处理剩余的错误字母，每三个错误字母（如A段中的B、B段中的C、C段中的A）需要两次交换。循环交换次数为剩余错误字母数量的2倍。

   • 总交换次数：直接交换次数 + 循环交换次数。

6. 取最小值：记录所有分组顺序中总交换次数的最小值。

   #include <iostream>
   #include <vector>
   #include <climits>
   #include <algorithm>
   using namespace std;int main() {string s;cin >> s;int n = s.length();// 统计B、A、T的数量int countB = count(s.begin(), s.end(), 'B');int countA = count(s.begin(), s.end(), 'A');int countT = count(s.begin(), s.end(), 'T');// 定义6种分组顺序vector<string> perms = {"BAT", "BTA", "ABT", "ATB", "TBA", "TAB"};int ans = INT_MAX;for (const string& perm : perms) {char a = perm[0], b = perm[1], c = perm[2];vector<int> cnt(3);// 根据当前分组顺序设置各字母的数量cnt[0] = (a == 'B') ? countB : (a == 'A') ? countA : countT;cnt[1] = (b == 'B') ? countB : (b == 'A') ? countA : countT;cnt[2] = (c == 'B') ? countB : (c == 'A') ? countA : countT;// 定义各段的起始和结束索引int segA_start = 0, segA_end = cnt[0];int segB_start = segA_end, segB_end = segA_end + cnt[1];int segC_start = segB_end, segC_end = n;// 统计各段中的错误字母int in_a_b = 0, in_a_c = 0;int in_b_a = 0, in_b_c = 0;int in_c_a = 0, in_c_b = 0;// 检查A段for (int i = segA_start; i < segA_end; i++) {if (s[i] == b) in_a_b++;else if (s[i] == c) in_a_c++;}// 检查B段for (int i = segB_start; i < segB_end; i++) {if (s[i] == a) in_b_a++;else if (s[i] == c) in_b_c++;}// 检查C段for (int i = segC_start; i < segC_end; i++) {if (s[i] == a) in_c_a++;else if (s[i] == b) in_c_b++;}// 计算直接交换次数int direct_swaps = min(in_a_b, in_b_a) + min(in_a_c, in_c_a) + min(in_b_c, in_c_b);// 计算剩余错误字母数量int remaining_errors = (in_a_b - min(in_a_b, in_b_a)) + (in_a_c - min(in_a_c, in_c_a));// 总交换次数 = 直接交换次数 + 2 * 剩余错误字母数量int total_swaps = direct_swaps + 2 * remaining_errors;ans = min(ans, total_swaps);}cout << ans << endl;return 0;
   }

   交换次数说明

7. 直接交换：处理可以两两配对并一次性归位的错误字母，每对交换次数为1。

8. 循环交换：处理剩余错误字母（形成循环依赖），每三个错误字母需要两次交换。例如，A段中的B、B段中的T、T段中的A，需两次交换才能全部归位。

9. 总交换次数：直接交换次数加上循环交换次数，所有分组顺序中的最小值即为最终答案。