求解使光束造成最小伤害所需的最少操作次数

嘿，咱们先把问题的核心逻辑掰扯清楚：要让机器人的总伤害降到最低，所有的射击指令S必须尽可能早执行——毕竟C是用来翻倍光束强度的，越早射击，用到的充能次数越少，单次伤害就越低。而我们唯一能做的操作是交换相邻的C和S（每次交换算1次操作），所以问题就转化为：把每个S移动到它能到达的最左侧合理位置（也就是在已经排好的S的右侧），累加每个S需要移动的步数，就是我们要找的最少操作次数。

具体操作步骤 #

• 初始化两个变量：target_pos（记录下一个S应该放置的目标位置，初始为0）和total_swaps（记录总操作次数，初始为0）。
• 遍历指令序列的每个字符，同时记录当前字符的索引i：
  • 如果当前字符是S：
    • 这个S从当前位置i移到target_pos需要的步数是i - target_pos，把这个数值加到total_swaps里。
    • 然后把target_pos加1（因为下一个S要放在这个S的右边）。
  • 如果当前字符是C：直接跳过，继续往后遍历就行——我们要把S往前移，C自然会被挤到后面。

实例演示 #

举个例子，假设指令序列是CCSS（索引0:C、1:C、2:S、3:S）：

1. 第一个S在索引2，target_pos是0，需要移动2-0=2步，total_swaps变成2，target_pos更新为1。
2. 第二个S在索引3，target_pos是1，需要移动3-1=2步，total_swaps变成2+2=4。
   最终序列变成SSCC，总伤害是1+1=2（这是这个序列能达到的最小伤害）。

再比如序列CSCS（0:C、1:S、2:C、3:S）：

1. 第一个S在索引1，移动到target_pos=0需要1步，total_swaps=1，target_pos更新为1。
2. 第二个S在索引3，移动到target_pos=1需要2步，total_swaps=1+2=3。
   最终序列是SSCC，总伤害同样是2。

代码实现（Python示例） #

def min_swaps_for_min_damage(program):
    target_pos = 0
    total_swaps = 0
    for idx, cmd in enumerate(program):
        if cmd == 'S':
            total_swaps += idx - target_pos
            target_pos += 1
    return total_swaps

# 测试用例
print(min_swaps_for_min_damage("CCSS"))  # 输出4
print(min_swaps_for_min_damage("CSCS"))  # 输出3
print(min_swaps_for_min_damage("SSCC"))  # 输出0（已经是最小伤害序列）

补充：如果是给定伤害上限的情况 #

如果问题变体是“给定最大允许伤害D，求把总伤害降到≤D所需的最少操作次数”，逻辑会稍有不同：

1. 先计算当前序列的总伤害，如果已经≤D，直接返回0。
2. 从右往左找第一个CS组合（因为把右边的CS换成SC，减少的伤害最多——这个S原本在多个C之后，移动后少乘一次2，伤害减少量是当前强度/2）。
3. 每次交换这个CS为SC，更新总伤害，直到总伤害≤D，统计交换次数即可。

内容的提问来源于stack exchange，提问作者Dylan