四口鲸鱼爱吃盐

用户名：uq_98591838827

访问量：1716

签　名：

等　　级
排　　名	483
经　　验	4680
参赛次数	0
文章发表	28
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-学霸的迷宫【Python题解】BFS
浏览：100

你可能喜欢

【Python题解】蓝桥杯基础练习VIP-完美的代价

　　作者: 四口鲸鱼爱吃盐　　　　发表时间：2023-03-02 17:05:23 浏览：146　|　评论：0　

原题链接：蓝桥杯基础练习VIP-完美的代价

# 解题思路
本题利用双指针，其中头指针 `head` 从前向后遍历，尾指针 `tail` 从后向前遍历。

**退出循环的条件：**
1. 字符串长度为偶数，但是有频数为奇数的字母
2. 字符串长度为奇数，但是有多于1个的频数为奇数的字母

具体思路见参考代码。

# 参考代码
```python
n = int(input())
s = list(input())
count = 0   # 记录交换次数
flag = 0    # 标记是否有字母频数为奇数
res = True

# 双指针
L = n - 1   # 头指针搜索范围，到倒数第2个
for head in range(L):
    # 对于每一个s[head]，用尾指针去搜索是否有相同的字母s[tail]
    for tail in range(L, head - 1, -1):
        # 指针tail搜索完毕，没有发现s[head] == s[tail]
        # 说明该字母频数为奇数 1，且该字母在回文序列中一定在中间
        if head == tail:
            # 如果字符串长度为偶数
            # 字符串长度为奇数，但是已经有 flag == 1
            if n%2 == 0 or flag == 1:
                res = False
                break
            flag = 1
            # (n//2 - head) 为将该字母移动到中间位置的交换次数
            count += n//2 - head
        # 发现了 s[head] == s[tail]
        elif s[head] == s[tail]:
            # 交换位置
            for i in range(tail, L):
                s[i], s[i+1] = s[i+1], s[i]
                count += 1
            L -= 1
            break

# 如果是impossible，退出外层循环
    if res == False:
        break

if res == False:
    print('Impossible')
else:
    print(count)
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

四口鲸鱼爱吃盐

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

求圆的面积（C语言代码）

【Python题解】蓝桥杯基础练习VIP-完美的代价

评论区

精彩推荐

A+B for Input-Output Practice (III) （C语言代码）

DNA （C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

C二级辅导-计负均正（C语言代码）

链表数据求和操作（C语言代码）

C语言训练-大、小写问题（C语言代码）

筛排处理（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言训练-百钱百鸡问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

四口鲸鱼爱吃盐

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

求圆的面积 （C语言代码）

【Python题解】蓝桥杯基础练习VIP-完美的代价

评论区

精彩推荐

A+B for Input-Output Practice (III) （C语言代码）

DNA （C语言代码）

蓝桥杯历届试题-翻硬币 （C++代码）

C二级辅导-计负均正 （C语言代码）

链表数据求和操作 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

筛排处理 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言训练-百钱百鸡问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

求圆的面积（C语言代码）

求圆的面积（C语言代码）

　　评论区

蓝桥杯历届试题-翻硬币（C++代码）

C二级辅导-计负均正（C语言代码）

链表数据求和操作（C语言代码）

C语言训练-大、小写问题（C语言代码）

筛排处理（C语言代码）

C语言训练-百钱百鸡问题（C语言代码）