备战蓝桥杯国赛【Day 18】-平芜编程栈

📌写在前面：今天的3道题全部来自蓝桥杯算法赛真题，难度梯度递进，核心考点包括：分离排序思想、贪心拼接策略、归并排序求逆序对、多关键字排序。这些题目看似简单，但暗藏精妙设计，是检验排序思维深度的绝佳试金石。

📚 今日刷题清单

题号	题目	来源	类型	难度	核心考点
1	奇偶排序	蓝桥杯17022	分离排序	⭐⭐	列表推导式、分离排序、稳定合并
2	二进制王国	蓝桥杯17035	贪心+自定义排序	⭐⭐⭐⭐	拼接比较、贪心证明、字典序最小
3	星际争霸	蓝桥杯5092	归并排序+逆序对	⭐⭐⭐⭐⭐	归并排序、逆序对计数、多关键字排序

一、奇偶排序 ⭐⭐

1.1 题目描述

给定n个整数，要求将所有奇数按升序排在前面，所有偶数按升序排在后面。

输入：n和数组a
输出：排序后的数组（奇数在前，偶数在后，各自升序）

1.2 关键思路：分离+分别排序+合并

暴力思路：遍历数组，奇数放前面，偶数放后面，然后各自排序。时间O(n log n)。
更优思路：利用 Python 列表推导式，一行分离奇偶，再分别排序合并。

核心洞察：

奇数和偶数的相对顺序不需要交错，可以完全分离
分离后各自排序，再拼接即可

1.3 推演验证

输入: n=6, a=[3, 1, 4, 1, 5, 9, 2, 6] 分离： 奇数: [3, 1, 1, 5, 9] 偶数: [4, 2, 6] 各自排序： 奇数: [1, 1, 3, 5, 9] 偶数: [2, 4, 6] 合并: [1, 1, 3, 5, 9, 2, 4, 6] 等等，样例输出应该是？ 假设输入: [3, 1, 4, 1, 5, 9, 2, 6] 奇数排序: [1, 1, 3, 5, 9] 偶数排序: [2, 4, 6] 输出: 1 1 3 5 9 2 4 6

1.4 题解

n=int(input())a=list(map(int,input().split()))# 分离奇数和偶数odd=[xforxinaifx%2==1]# 奇数even=[xforxinaifx%2==0]# 偶数# 各自排序后合并输出print(*(sorted(odd)+sorted(even)))

复杂度：时间O(n log n)（排序），空间O(n)

1.5 关键细节

坑点	说明
`x % 2 == 1`判断奇数	Python中负数取模结果可能为负，但题目数据通常为正整数
*``解包输出**	`print(*(list))`等价于`print(list[0], list[1], ...)`，去掉方括号
列表推导式效率	`O(n)`遍历，比`filter`更 Pythonic
稳定排序	`sorted()`是稳定排序，相等元素相对顺序不变

二、二进制王国 ⭐⭐⭐⭐

2.1 题目描述

给定n个二进制字符串，将它们拼接起来，求字典序最小的拼接结果。

输入：n和n个二进制字符串
输出：字典序最小的拼接字符串

2.2 关键思路：自定义比较器贪心

暴力思路：枚举所有排列，拼接后比较字典序。n!种排列，不可接受。
优化思路：贪心策略——a应该在b前面，当且仅当a+b < b+a（字符串拼接后字典序比较）。

为什么a+b < b+a是对的？

证明思路（交换论证）：

假设最优排列中，存在相邻两个字符串a, b，满足a+b > b+a
交换它们得到..., b, a, ...
比较两种排列：... + a + b + ...vs... + b + a + ...
由于a+b > b+a，交换后字典序更小，与"最优"矛盾！
所以最优排列中，任意相邻两个都满足a+b ≤ b+a

传递性：这种比较关系满足传递性（可以严格证明），所以可以用排序实现。

2.3 推演验证

输入: n=3, s=["10", "1", "11"] 所有排列及拼接结果： ["10","1","11"] → "10111" ["10","11","1"] → "10111" ["1","10","11"] → "11011" ["1","11","10"] → "11110" ["11","1","10"] → "11110" ["11","10","1"] → "11101" 字典序最小: "10111" 用贪心策略验证： 比较 "10" 和 "1": "10"+"1" = "101", "1"+"10" = "110" "101" < "110"，所以 "10" 应该在 "1" 前面 比较 "10" 和 "11": "10"+"11" = "1011", "11"+"10" = "1110" "1011" < "1110"，所以 "10" 在 "11" 前面 比较 "1" 和 "11": "1"+"11" = "111", "11"+"1" = "111" 相等，相对顺序不变（稳定排序） 排序结果: ["10", "1", "11"] 或 ["10", "11", "1"] 拼接: "10111" ✓

2.4 题解

fromfunctoolsimportcmp_to_key n=int(input())s=[]for_inrange(n):s.append(input().strip())defcompare(a,b):""" 比较函数：a+b 和 b+a 的字典序 返回 -1: a 排在 b 前面（a+b < b+a） 返回 1: a 排在 b 后面（a+b > b+a） 返回 0: 相等 """ifa+b<b+a:return-1elifa+b>b+a:return1else:return0# 自定义排序s.sort(key=cmp_to_key(compare))# 拼接输出print(''.join(s))

复杂度：时间O(n log n × L)，L为字符串平均长度

2.5 关键细节

坑点	说明
`a+b < b+a`不是`a < b`	直接比较字符串本身是错误的！必须用拼接后比较
`cmp_to_key`用法	Python3 标准写法，将比较函数转为 key 函数
稳定排序	当`a+b == b+a`时返回0，保持原有相对顺序
字符串拼接复杂度	每次比较`O(L)`，总复杂度`O(n log n × L)`
输入读取	`input().strip()`去除首尾空白，避免换行符干扰

三、星际争霸 ⭐⭐⭐⭐⭐

3.1 题目描述

星际争霸中，每个士兵有一个战斗力字符串（由0-9组成）。定义一个字符串的混乱度为：将其转换成列表后，逆序对的个数。

现在给定n个士兵的战斗力字符串，按以下规则排序：

混乱度升序（逆序对数小的在前）
混乱度相同，字符串长度升序
长度也相同，字符串本身字典序升序

输入：n和n个字符串
输出：排序后的字符串列表

3.2 关键思路：归并排序求逆序对 + 多关键字排序

第一步：求逆序对个数

逆序对定义：数组中i < j但a[i] > a[j]的对数。

归并排序求逆序对：

归并排序的分治过程中，当arr[i] > arr[j]时，arr[i...m]都大于arr[j]，贡献m-i+1个逆序对
时间O(n log n)

第二步：多关键字排序

排序规则：

第一关键字：逆序对数（升序）
第二关键字：字符串长度（升序）
第三关键字：字符串本身（字典序升序）

Python 实现：arr.sort(key=lambda x: (x[0], len(x[1]), x[1]))

3.3 推演验证

输入: n=3 s = ["21", "123", "321"] 计算逆序对： "21" → [2,1] → 逆序对: (2,1) → 1个 "123" → [1,2,3] → 逆序对: 0个 "321" → [3,2,1] → 逆序对: (3,2),(3,1),(2,1) → 3个 排序： ("123", 0, 3) → 第一 ("21", 1, 2) → 第二 ("321", 3, 3) → 第三 输出: 123, 21, 321

3.4 题解

defmerge_sort(arr,l,r):""" 归并排序，同时计算逆序对个数 arr: 待排序数组（整数列表） l, r: 左右边界（闭区间） 返回: 逆序对个数 """ifl>=r:return0m=(l+r)//2left=merge_sort(arr,l,m)# 左半部分逆序对right=merge_sort(arr,m+1,r)# 右半部分逆序对returnleft+right+merge(arr,l,m,r)# 跨区间逆序对defmerge(arr,l,m,r):""" 合并两个有序区间 [l,m] 和 [m+1,r] 同时计算跨区间逆序对 """temp=[0]*(r-l+1)# 临时数组i=l# 左半部分指针j=m+1# 右半部分指针idx=0# temp数组指针res=0# 逆序对计数# 双指针合并whilei<=mandj<=r:ifarr[i]<=arr[j]:# 左边小，直接放入temp[idx]=arr[i]i+=1else:# 右边小，说明 arr[i...m] 都大于 arr[j]# 贡献 m - i + 1 个逆序对res+=m-i+1temp[idx]=arr[j]j+=1idx+=1# 处理剩余元素whilei<=m:temp[idx]=arr[i]i+=1idx+=1whilej<=r:temp[idx]=arr[j]j+=1idx+=1# 复制回原数组arr[l:r+1]=tempreturnres# 主程序n=int(input())arr=[]for_inrange(n):s=input().strip()# 将字符串转为整数列表，计算逆序对num_list=list(s)# 如 "21" → ['2', '1']inversion_count=merge_sort(num_list,0,len(num_list)-1)# 保存 (逆序对数, 原字符串)arr.append((inversion_count,s))# 多关键字排序：# 1. 逆序对数升序# 2. 字符串长度升序# 3. 字符串字典序升序arr.sort(key=lambdax:(x[0],len(x[1]),x[1]))# 输出结果forinfoinarr:print(info[1])

复杂度：

计算逆序对：O(L log L)，L为字符串长度
总时间：O(n × L log L + n log n)
空间：O(L)（归并排序临时数组）

3.5 关键细节

坑点	说明
归并排序中的`arr[i] <= arr[j]`	必须是`<=`不是`<`，保证稳定性，避免重复计数
`res += m - i + 1`	当`arr[i] > arr[j]`时，`arr[i...m]`都大于`arr[j]`，共`m-i+1`个
字符串转列表	`list(s)`得到字符列表，`merge_sort`按字符 ASCII 比较
多关键字排序	`key=lambda x: (x[0], len(x[1]), x[1])`元组逐元素比较
临时数组大小	`temp = [0] * (r - l + 1)`，注意是闭区间，长度`r-l+1`

3.6 归并排序求逆序对原理

数组: [3, 1, 4, 2] (索引0~3) 分治过程: [3,1,4,2] → [3,1] 和 [4,2] [3,1] → [3] 和 [1] 合并: 3 > 1，res += 1-0+1 = 1（3的逆序对） 结果: [1,3], res=1 [4,2] → [4] 和 [2] 合并: 4 > 2，res += 1-0+1 = 1（4的逆序对） 结果: [2,4], res=1 合并 [1,3] 和 [2,4]: i=0(1), j=2(2): 1 <= 2, 放入1, i=1 i=1(3), j=2(2): 3 > 2, res += 2-1+1 = 2（3和2, 3后面的...等等） 等等，m=1（左半部分最后一个索引） i=1(3), j=2(2): 3 > 2, res += m - i + 1 = 1 - 1 + 1 = 1 放入2, j=3 i=1(3), j=3(4): 3 <= 4, 放入3, i=2（左半部分结束） 放入4 总逆序对: 1 + 1 + 1 = 3 验证: (3,1), (3,2), (4,2) → 3个 ✓

🎯 今日复盘总结

题目	核心技巧	思维路径	易错点	国赛价值
奇偶排序	分离排序	奇偶分离→各自排序→合并	`*`解包输出、列表推导式	基础技巧
二进制王国	贪心拼接排序	相邻交换论证→`a+b<b+a`→自定义排序	比较器返回值、字符串拼接方向	经典贪心
星际争霸	归并排序+逆序对	分治求逆序对→多关键字排序	`<=`稳定性、`m-i+1`计数、多关键字	综合应用

💡 今日核心收获

分离排序思想：当数据可以清晰分类时，先分离再各自排序，最后合并，往往比复杂比较器更简洁。
贪心拼接策略：a+b < b+a是解决"拼接最值"类问题的通用贪心策略，记住交换论证的证明方法。
归并排序求逆序对：分治过程中统计跨区间逆序对，时间O(n log n)，是处理"顺序对/逆序对"问题的标准算法。
多关键字排序：Python 中用元组key=lambda x: (key1, key2, key3)，逐元素比较，简洁高效。
稳定排序的重要性：当比较相等时，稳定排序保持原有顺序，这在多轮排序或复杂规则中至关重要。

📌 排序算法复杂度对比

算法	平均时间	最坏时间	空间	稳定性	Python实现
冒泡排序	`O(n²)`	`O(n²)`	`O(1)`	✅	—
选择排序	`O(n²)`	`O(n²)`	`O(1)`	❌	—
插入排序	`O(n²)`	`O(n²)`	`O(1)`	✅	—
归并排序	`O(n log n)`	`O(n log n)`	`O(n)`	✅	`sorted()`/`sort()`
快速排序	`O(n log n)`	`O(n²)`	`O(log n)`	❌	—
堆排序	`O(n log n)`	`O(n log n)`	`O(1)`	❌	`heapq`
Timsort	`O(n log n)`	`O(n log n)`	`O(n)`	✅	Python内置