蓝桥杯python备赛笔记之（三）贪心&排序

2026-01-29 16:39:13 栏目：最新资讯 3 阅读

整篇笔记共分为十章，都是博主在准备25年蓝桥杯时所写，听的网课是这个，讲的非常好，很适合零基础速成，如果有听不懂的可以多听几遍

https://www.bilibili.com/video/BV1Zs9VYrEgg?spm_id_from=333.788.videopod.sections&vd_source=5edde23df276e6fb4a94821fa44f38b5

目录如下：

1.Python语法基础及算法入门
2.语法进阶&常用数据结构&算法入门
3.贪心&排序
4.哈希&暴力&前缀
5.二分查找&二分答案
6.搜索&BFS&DFS
7.[数据结构]并查集&堆
8.动态规划
9.图论
10.数论基础&日期问题

一、贪心算法

（一）核心思想

贪心算法的核心是在每一步决策中选择当前最优解，通过局部最优积累实现全局最优（适用于满足 “贪心选择性质” 和 “最优子结构性质” 的问题）。本章聚焦 “团购问题”，核心策略为：尽可能多的进行团购，直至团购不再划算时停止。

（二）典型例题：训练士兵

问题场景：通过团购或单独付费的方式为士兵提供训练，需计算最低总成本。
输入说明：
- n：士兵人数
- S：团购单次成本
- 每组输入数据包含两个值：p（单人训练成本）、c（该士兵需要的训练次数）
算法思路：
- 数据预处理：将士兵数据按 “训练次数（c）” 升序排序，确保从训练次数最少的士兵开始处理
- 成本判断：维护所有未处理士兵的单人成本总和（tot），若 tot ≥ 团购成本 S，则团购更划算；否则选择单人付费
- 累计成本：按训练次数的差值分段计算成本，更新已处理的训练次数（cnt）和剩余士兵的单人成本总和（tot）

完整代码：

import sys
input = lambda: sys.stdin.readline().strip()
n, S = map(int, input().split())
nums = [[0, 0]] * n  # 存储士兵的（单人成本p，训练次数c）
p, c = [0] * n, [0] * n  # 分别存储单人成本和训练次数
# 数据预处理：读取输入并存储
for i in range(n):
    nums[i] = list(map(int, input().split()))
# 按训练次数（nums[i][1]）升序排序
nums.sort(key=lambda x: x[1])
# 拆分p和c数组
for i in range(n):
    p[i], c[i] = nums[i][0], nums[i][1]
res = cnt = 0  # res：总费用；cnt：已处理的训练次数
tot = sum(p)  # 所有未处理士兵的单人成本总和
for i in range(n):
    if tot >= S:
        # 团购划算，按次数差值计算团购费用
        res += (c[i] - cnt) * S
        cnt = c[i]  # 更新已处理的训练次数
    else:
        # 团购不划算，按单人成本计算费用
        res += (c[i] - cnt) * p[i]
    tot -= p[i]  # 当前士兵处理完成，从总和中减去其单人成本
print(res)

二、排序

（一）插入排序应用：根据身高重建队列

问题场景：给定士兵的身高（h）和 “前面比自己高或等高的人数（k）”，重建符合要求的队列。
输入示例：people = [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
算法思路：
- 排序规则：先按身高（h）降序排序，若身高相同则按 k 值升序排序（确保高个子先占位，不影响矮个子的 k 值判断）
- 插入逻辑：遍历排序后的数组，根据每个士兵的 k 值，将其插入到结果列表的第 k 个位置（k 值即为其在当前结果列表中的目标索引）

完整代码：

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 排序：先按身高h降序，再按k值升序（两种等价写法）
        # 写法1：利用lambda表达式多关键字排序
        people.sort(key=lambda x: (-x[0], x[1]))
        # 写法2：通过放大h的权重实现降序优先级（原文档写法，等价于写法1）
        # people.sort(key=lambda x: -x[0] * 10**5 + x[1])
        
        res = []
        # 遍历排序后的数组，按k值插入对应位置
        for i, p in enumerate(people):
            h, k = p[0], p[1]
            if k == i:
                # k值与当前结果列表长度一致，直接追加
                res.append(p)
            elif k < i:
                # 插入到第k个索引位置
                res.insert(k, p)
        return res

输出结果：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

（二）关键技术：enumerate 函数

功能：遍历可迭代对象时，同时获取元素的索引（index）和对应值（item）
语法格式：for idx, item in enumerate(iterable, start=0)
- idx：元素的索引值
- item：可迭代对象中的单个元素
- iterable：需要遍历的可迭代对象（如列表、元组、字符串等）
- start：索引起始值（可选参数，默认值为 0）

示例：

lst = ["a", "b", "c"]
for idx, item in enumerate(lst, start=1):
    print(f"索引：{idx}，元素：{item}")
# 输出：
# 索引：1，元素：a
# 索引：2，元素：b
# 索引：3，元素：c

（三）二维排序规则

适用场景：对二维列表（每个元素为子列表）按多个关键字排序
核心语法：list.sort(key=lambda x: (排序关键字1, 排序关键字2, ...))
本章核心排序规则：people.sort(key=lambda x: (-x[0], x[1]))
- 第一关键字：-x [0]（负号表示降序），按二维列表第一个元素（身高 h）降序排序
- 第二关键字：x [1]（默认升序），按二维列表第二个元素（k 值）升序排序
补充说明：原文档中-x[0] * 10**5 + x[1]的写法，本质是通过放大第一关键字的权重，确保身高降序的优先级高于 k 值升序，与(-x[0], x[1])等价，适用于需要明确优先级的多关键字排序场景。