[蓝桥杯]交换次数

交换次数

题目描述

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. 总交换次数：直接交换次数加上循环交换次数，所有分组顺序中的最小值即为最终答案。