227.2018年蓝桥杯国赛 - 交换次数（中等）- 贪心

227. 交换次数（贪心）

1. 2018年蓝桥杯国赛 - 交换次数（中等）

标签：2018 暴力 国赛

1.1 题目描述

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

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

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

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

1.2 输入描述

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

1.3 输出描述

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

1.4 输入输出样例

示例：

输入

TABTABBTTTT

输出

3

1.5 运行限制

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

2. 解题思路

2.1 问题的本质

这道题的本质是找到一个新的排列方式，使得相同字符的位置尽量挨在一起。我们可以把目标设定为将字符 B、A、T 分别排成一个连续的区块。

2.2 目标排列方式

我们首先考虑所有可能的字符排列（B、A、T 的排列方式），它们分别是：

2.3 数学公式推导

对于每一种排列方式，我们将字符串分成三部分：B 的部分、A 的部分和 T 的部分。

假设我们当前目标排列为 'ABT'，那么：

• 第一部分是 B 的区域；
• 第二部分是 A 的区域；
• 第三部分是 T 的区域。

设定每个部分的字符数量为 an、bn 和 tn，其中 an、bn 和 tn 分别表示 B、A、T 在目标排列中应占的字符数量。

误占字符的数量可以用以下公式计算：

• ab：在 B 的区域中，错误放置了 A 的数量；
• at：在 B 的区域中，错误放置了 T 的数量；
• ba：在 A 的区域中，错误放置了 B 的数量；
• bt：在 A 的区域中，错误放置了 T 的数量。

最终的交换次数 c 可通过以下公式计算：
$$c=ab+at+ba+bt-\min (ba,ab)$$

解释：

1. ab 和 ba 分别表示 B 和 A 在错误区域中的数量；

2. at 和 bt 分别表示 A 和 T 在错误区域中的数量；

3. $\min (ba,ab)$ 是为了避免重复计算两个交换的次数，即如果 A 和 B 之间的交换可以同时解决两个问题，那么就减去一次交换次数。

2.4 算法流程

通过尝试六种目标排列（'ABT'、'ATB'、'BAT'、'BTA'、'TAB'、'TBA'），计算每一种排列下的交换次数，最后选择最小的交换次数。

3. 代码实现

# 读取输入
s = str(input())

# 定义所有可能的目标排列方式
st = ['ABT', 'ATB', 'BAT', 'BTA', 'TAB', 'TBA']

# 用来保存每种目标排列的最小交换次数
ans = []

# 遍历所有目标排列
for i in range(6):
    a = st[i][0]  # 当前目标排列的第一个字符
    b = st[i][1]  # 当前目标排列的第二个字符
    t = st[i][2]  # 当前目标排列的第三个字符

    # 计算每个字符的出现次数
    an = s.count(a)  # a的个数
    bn = s.count(b)  # b的个数

    # 在目标区间内错误的字符数量
    ab = s[:an].count(b)  # 在 a 的位置上，b误占的数量
    at = s[:an].count(t)  # 在 a 的位置上，t误占的数量

    ba = s[an:an+bn].count(a)  # 在 b 的位置上，a误占的数量
    bt = s[an:an+bn].count(t)  # 在 b 的位置上，t误占的数量

    # 计算交换次数，最小化交换次数
    c = ab + at + ba + bt - min(ba, ab)

    # 将当前排列的交换次数加入答案列表
    ans.append(c)

# 输出最小交换次数
print(min(ans))

4. 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串长度。我们对每种排列执行 $O(n)$ 次操作，共 6 种排列，因此总体时间复杂度为 $O(6n)$，即 $O(n)$。
• 空间复杂度：$O(1)$，算法使用了固定大小的常量空间，除了输入字符串和少量临时变量外，没有额外的空间开销。