贪心算法与交换论证

import sys

data = sys.stdin.read().split()
n = int(data[0])
shows = []
for i in range(n):
    t, l = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    shows.append((t, t + l))                  # (开始, 结束)
shows.sort(key=lambda s: s[1])                # 排序键：结束时间早的在前
count = 0
cur_end = -10**9                              # 已选的最后一场的结束时间（初始：无）
for start, end in shows:
    if start >= cur_end + 15:                 # 选取条件：开始时间 ≥ 上一场结束 + 15 分钟转场（等号成立：「至少 15 分钟」）
        count += 1
        cur_end = end
print(count)

选取条件里的 + 15 与 >= 缺一不可：分别用第 05 节的四场演出（3）和 2 / 0 60 / 70 60（1）核对；题目页参考题解按开始时间排序 + 替换，结果相同。

import sys

data = sys.stdin.read().split()
limit, n = int(data[0]), int(data[1])
weight = sorted(int(x) for x in data[2:2 + n])   # 轻的在前、重的在后
l, r = 0, n - 1
boats = 0
while l <= r:                                 # 每轮处理最重的 weight[r]
    if weight[l] + weight[r] <= limit:        # 最轻的能和最重的同船
        l += 1
    r -= 1                                    # 无论配没配上，最重的这个人都上船了
    boats += 1
print(boats)

用题面示例 3 4 / 3 2 2 1 → 3 与第 06 节的 10 5 / 9 8 7 2 1 → 3 核对。

import sys

s = sys.stdin.readline().strip()
remain = {}                                   # 每个数字后面还剩几次可用
for ch in s:
    remain[ch] = remain.get(ch, 0) + 1
stack = []                                    # 从栈底到栈顶递减：大数字尽量靠前
in_stack = set()                              # 当前已在栈里的数字（每个数字最终只出现一次）
for ch in s:
    remain[ch] -= 1                           # 走过一个，它的剩余次数减 1
    if ch in in_stack:
        continue                              # 已经用过：直接跳过（保留前面那个位置）
    while stack and stack[-1] < ch and remain[stack[-1]] > 0:   # 栈顶比当前小、且后面还有同数字可用 → 弹掉
        in_stack.remove(stack.pop())
    stack.append(ch)
    in_stack.add(ch)
print("".join(stack))

用题面示例 12341 → 2341、42234 → 423 核对；思路与题目页参考题解相同（计数 + 已用集合 + 单调栈）。

def max_shows(shows, gap=15):
    # shows: [(开始, 结束)]；连续两场之间至少 gap 分钟
    order = sorted(shows, key=lambda s: s[1])    # 排序键：结束时间
    count, cur_end = 0, -10**9
    for start, end in order:
        if start >= cur_end + gap:               # 选取条件：写进比较式，不改排序键
            count += 1
            cur_end = end
    return count

assert max_shows([(600, 660), (630, 690), (700, 760), (775, 835)]) == 3   # 第 05 节表；775 = 760 + 15 恰好可选
assert max_shows([(0, 100), (1, 2), (30, 31)]) == 2                      # 按开始时间只得 1
assert max_shows([(0, 20), (35, 55), (22, 32)]) == 2                     # 按时长只得 1
assert max_shows([(0, 60), (70, 130)]) == 1                              # 转场不够 15 分钟
assert max_shows([(0, 60), (70, 130)], gap=0) == 2                       # 练习 2：去掉转场

gap 作为参数：附加规则只出现在选取条件里。

def min_boats(limit, weights):
    w = sorted(weights)
    l, r = 0, len(w) - 1
    boats = 0
    while l <= r:                                 # 每轮处理最重的 w[r]
        if w[l] + w[r] <= limit:                  # 最轻的能同船就带上
            l += 1
        r -= 1
        boats += 1
    return boats

assert min_boats(3, [3, 2, 2, 1]) == 3            # P3118 题面示例（与「救生艇」示例相同）
assert min_boats(5, [1, 2, 3]) == 2               # l == r 时那个人单独一条船
assert min_boats(10, [9, 8, 7, 2, 1]) == 3        # 轻配轻会得 4
assert min_boats(10, [1, 9, 2, 8]) == 2           # 不排序会得 3
assert min_boats(4, [4]) == 1

五条断言分别对应第 06 节与第 09 节的用例。