算法模板 - 搜索与基础技巧

本文整理搜索和基础编程技巧的模板，按难度递增排列：竞赛 I/O → 自定义排序 → 排序算法 → 双向 BFS。

1. 竞赛常用 I/O

ACM/OI 竞赛中 Python 的输入输出技巧。大量数据时，sys.stdin / sys.stdout 比 input() / print() 快很多。

# === 输入 ===

# 读一行整数
a, b = map(int, input().split())

# 读一行到列表
lst = list(map(int, input().split()))

# 读 n 行，每行多个整数
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

# 大量输入时用 sys.stdin 更快（约 5-10 倍）
import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
    line = input().strip()

# === 输出 ===

# 保留小数位
print(f"{3.14159:.2f}")  # 3.14

# 列表输出为空格分隔
print(*[1, 2, 3])  # 1 2 3

# 大量输出时用 sys.stdout.write 更快
import sys
out = []
for x in [1, 2, 3]:
    out.append(str(x))
sys.stdout.write(" ".join(out) + "\n")

为什么 sys.stdin.readline 比 input() 快？ input() 内部会调用 sys.stdin.readline() 并额外做 strip('\n')。当你需要处理 10^5+ 行输入时，这个额外操作的开销就不可忽略了。

---

2. 自定义排序

2.1 重写 __lt__

在 Python 中，sorted() 和 heapq 默认使用 < 运算符比较。通过重写 __lt__ 方法可以自定义排序规则。

class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score

    def __lt__(self, other):
        """排序规则：分数升序，分数相同按姓名降序"""
        if self.score != other.score:
            return self.score < other.score
        return self.name > other.name

students = [Student("Alice", 90), Student("Bob", 85), Student("Charlie", 90)]
for s in sorted(students):
    print(f"{s.name}: {s.score}")
# Bob: 85
# Charlie: 90
# Alice: 90

2.2 使用 key 函数

更常见的做法是用 key 参数，代码更简洁：

students = [("Alice", 90), ("Bob", 85), ("Charlie", 90)]

# 按分数升序，分数相同按姓名降序
result = sorted(students, key=lambda s: (s[1], s[0]), reverse=False)
# 注意：key 函数不能直接做"某字段升序+某字段降序"的混合排序
# 需要 trick：对降序字段取负（数值）或用 __lt__

key vs __lt__：简单排序用 key，复杂混合排序用 __lt__。key 函数对每个元素只调用一次，排序过程中直接比较 key 值，效率更高。

---

3. 排序算法

3.1 选择排序

核心思想：每轮从未排序部分选最小的，放到已排序部分的末尾。

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]

特点：O(n²)，不稳定（交换可能改变相等元素的相对顺序），但交换次数最少（最多 n-1 次）。

3.2 归并排序

核心思想：分治。把数组分成两半，分别排序，再合并。合并时用双指针，O(n) 完成。

def merge_sort(lst, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort(lst, left, mid)
    merge_sort(lst, mid + 1, right)

    # 合并两个有序子数组
    i, j = left, mid + 1
    temp = []
    while i <= mid and j <= right:
        if lst[i] <= lst[j]:
            temp.append(lst[i]); i += 1
        else:
            temp.append(lst[j]); j += 1
    temp.extend(lst[i:mid + 1])
    temp.extend(lst[j:right + 1])
    lst[left:right + 1] = temp

特点：O(n log n)，稳定，需要 O(n) 额外空间。常用于逆序对计数（在合并时统计）。

3.3 快速排序

核心思想：选一个基准值，把数组分成"小于基准"和"大于基准"两部分，递归排序。

def quick_sort(lst, left, right):
    if left >= right:
        return
    # 三数取中选基准（避免最坏情况）
    mid = (left + right) // 2
    lst[mid], lst[right] = lst[right], lst[mid]

    pivot = lst[right]
    i, j = left, right - 1
    while i <= j:
        while i <= j and lst[i] < pivot:
            i += 1
        while i <= j and lst[j] >= pivot:
            j -= 1
        if i < j:
            lst[i], lst[j] = lst[j], lst[i]
    lst[i], lst[right] = lst[right], lst[i]

    quick_sort(lst, left, i - 1)
    quick_sort(lst, i + 1, right)

特点：平均 O(n log n)，最坏 O(n²)（已排序数组 + 取首元素为基准），不稳定，原地排序。

三种排序对比：

算法	时间（平均）	时间（最坏）	稳定性	空间
选择排序	O(n²)	O(n²)	不稳定	O(1)
归并排序	O(n log n)	O(n log n)	稳定	O(n)
快速排序	O(n log n)	O(n²)	不稳定	O(log n)

---

4. 双向 BFS

适用场景：求起点到终点的最短路径，且状态空间较大。

核心思想：同时从起点和终点出发，每次扩展较小的那一侧，当两个方向"相遇"时得到答案。

为什么比单向 BFS 快？ 假设每个节点有 b 个邻居，搜索深度为 d。单向 BFS 需要探索 O(b^d) 个节点。双向 BFS 只需要 O(b^(d/2) + b^(d/2)) = O(2 · b^(d/2))，当 d 较大时差距巨大。

from collections import deque

def bidirectional_bfs(start, end, get_neighbors):
    """
    双向 BFS 模板

    参数:
        start: 起始状态
        end: 目标状态
        get_neighbors: 函数，输入当前状态，返回所有可达的邻居状态
    返回:
        最短路径长度，不可达返回 -1
    """
    if start == end:
        return 0

    # 两个方向的队列和已访问集合（记录距离）
    q_start = deque([start])
    dist_start = {start: 0}
    q_end = deque([end])
    dist_end = {end: 0}

    while q_start and q_end:
        # 每次扩展较小的一侧
        if len(q_start) <= len(q_end):
            q, dist, other_dist = q_start, dist_start, dist_end
        else:
            q, dist, other_dist = q_end, dist_end, dist_start

        for _ in range(len(q)):
            current = q.popleft()
            for neighbor in get_neighbors(current):
                if neighbor in dist:
                    continue
                # 如果邻居在另一侧已访问，相遇！
                if neighbor in other_dist:
                    return dist[current] + 1 + other_dist[neighbor]
                dist[neighbor] = dist[current] + 1
                q.append(neighbor)

    return -1

例题：0 变成 20240701

def get_neighbors(num):
    """正向扩展：-1 或 ×2"""
    return [num - 1, 2 * num]

result = bidirectional_bfs(0, 20240701, get_neighbors)
print(result)  # 最短操作次数

双向 BFS 的关键细节：每次必须扩展较小的那一侧。如果总是扩展同一侧，就退化成了单向 BFS。

---

总结

算法	时间复杂度	核心思想
竞赛 I/O	—	sys.stdin / sys.stdout 加速
自定义排序	O(n log n)	__lt__ 或 key 函数
选择排序	O(n²)	每轮选最小
归并排序	O(n log n)	分治合并
快速排序	O(n log n) 平均	分治划分
双向 BFS	O(b^(d/2))	两端同时搜索，相遇即停

模板源码：AlgorithmLearning