【贪心】 —— 蓝桥杯基础练习——完美的代价

本题思路大体上是用第一个字符串，去寻找倒序后存在相同字符的位置，该位置是交换的次数（不明白的话可以举例），之后对原字符串进行交换操作，需要注意的是，交换完成的字符可以弹出，因为我们是从第一个字符开始找的，弹出后不影响之后字符的交换次数

另外一个需要注意的点是，当我们遇到奇数字符时，交换次数为当前字符长度的一半（len//2），但是这里我们选择不进行交换，直到所有偶数字符完成交换完再进行该奇数字符的交换，这样才能符合贪心策略。

至于为什么要这样做，是因为如果你遇到奇数字符，当把该字符放到字符串中间的时候，很可能被下一个偶数字符又交换至旁边，使其不再中间位置，使得最后交换次数增加，贪心失败。因此，直接将奇数字符放到最后进行交换，更符合贪心策略。

代码如下

n = int(input())
s = list(input())
count = 0 # 总的交换次数
m = 0 # 奇数个字符的数量
while len(s) > 1:
    flag = 0
    x = s[0]    # 和待交换字符相同的字符
    sr = s[::-1]
    for i in range(len(s) - 1):
        if sr[i] == x:
            flag = 1
            count += i
            # 交换字符
            for j in range(len(s) - i - 1, len(s) - 1):
                s[j], s[j + 1] = s[j + 1], s[i]
            s.pop(0)
            s.pop(-1)
            break
    # 出现奇数字符
    if flag == 0:
        m += 1
        if m > 1:   # 出现多个奇数字符，直接结束
            break
        else:
            count += len(s) // 2
            #for k in range(0, len(s)//2):
            #    s[k], s[k + 1] = s[k + 1], s[k]
            s.pop(0)
if m > 1:
    print('Impossible')
else:
    print(count)