二分边界与二分答案

import sys

lines = sys.stdin.read().split("\n")
nums = [int(x) for x in lines[0].strip().split(",")]   # 已按学号升序
target = int(lines[1].strip())

lo, hi = 0, len(nums)                      # 半开区间 [lo, hi)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] >= target:                # mid 满足「≥ 学号」→ 答案在 mid 或左边
        hi = mid
    else:
        lo = mid + 1                       # mid 不满足 → 答案在 mid 右边
print(lo + 1)                              # 题目位置从 1 起

自测用例：题面示例（110 → 6）与两个边界（90 → 1、200 → 8）。

import sys

lines = sys.stdin.read().split("\n")
piles = [int(x) for x in lines[0].split()]   # 第一行：每棵树的蟠桃数
h = int(lines[1].strip())                    # 第二行：小时数

def check(k):                                # 速度 k 能否在 h 小时内吃完
    hours = 0
    for p in piles:
        hours += (p + k - 1) // k            # 上取整：这棵树要几个小时
    return hours <= h

if len(piles) > h:                           # 每小时最多一棵树：树比小时多必无解
    print(0)
else:
    lo, hi = 1, max(piles)                   # 速度 = 最大堆时每棵 1 小时，一定可行
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                         # 可行 → 更小的速度可能也行
        else:
            lo = mid + 1                     # 不可行 → 至少要比 mid 大
    print(lo)

自测用例：第 05 节三组手算（→ 4、0、30）与练习 3 的 H=6（→ 23）。

import sys

data = sys.stdin.read().split()
m = int(data[0])
trees = sorted(int(x) for x in data[1:1 + m])   # 坑位坐标，先排序
n = int(data[1 + m])                            # 要种的棵数

def check(d):                                   # 最小间距为 d 时能否种下 n 棵
    count = 1                                   # 第一个坑一定种
    last = trees[0]
    for x in trees[1:]:
        if x - last >= d:
            count += 1
            last = x
            if count >= n:
                return True
    return count >= n

lo, hi = 1, trees[-1] - trees[0]                # 答案在 [1, 最大跨度] 内
while lo < hi:
    mid = (lo + hi + 1) // 2                    # 求最大可行值：mid 上取整
    if check(mid):
        lo = mid                                # 可行 → 更大的间距可能也行
    else:
        hi = mid - 1                            # 不可行 → 比 mid 小
print(lo)

自测用例：第 06 节逐轮表（→ 3）、练习 5（→ 9）、全部坑位都种的 3 / 1 2 3 / 3（→ 1）。输入格式按题目页参考题解（M / 坐标 / N）。

import sys
from math import gcd

lines = sys.stdin.read().split("\n")
work = sorted((int(x) for x in lines[0].replace(",", " ").split()), reverse=True)   # 工作量降序；先把逗号换成空格，两种排版都能读
n = int(lines[1].strip())                                          # 人数

g = 0
for x in work:
    g = gcd(g, x)                          # 所有工作量的最大公约数：每个人的总量一定是它的倍数

def check(limit):                          # 每人不超过 limit，能否把全部需求分给 n 个人
    limit -= limit % g                     # 总量只能是 g 的倍数：上限先降到 g 的倍数（全是偶数配奇数上限就靠这一步排除）
    if work[0] > limit:
        return False
    if sum(1 for x in work if 2 * x > limit) > n:   # 超过半容量的件互相不能同人
        return False
    failed = set()                         # 记住已证明「分不下去」的状态：(剩余工作量元组, 剩余人数)

    def solve(items, people):              # items：还没分配的工作量（降序元组）；people：还剩几个人
        if not items:
            return True
        if people == 0 or sum(items) > people * limit:   # 剩余总量装不进剩余的人
            return False
        if (items, people) in failed:
            return False
        first, rest = items[0], items[1:]  # 最大的一件必须归「当前这个人」（谁先拿都一样，直接指定）
        k = len(rest)

        def fill(start, cap, taken):       # 从 rest[start:] 里再挑一些和 first 一起放，剩余容量 cap
            for j in range(start, k):
                if rest[j] > cap:
                    continue
                if j > start and rest[j] == rest[j - 1] and (j - 1) not in taken:
                    continue               # 相同工作量的两件，只按顺序取，避免重复组合
                taken.add(j)
                if fill(j + 1, cap - rest[j], taken):
                    return True
                taken.discard(j)
            # 不再挑了：只有「剩下的件一件也放不进」这种装到最满的组合才值得往下试
            for j in range(k - 1, -1, -1):
                if j not in taken:
                    if rest[j] <= cap:     # 还有件放得进却没放：这种组合不如把它放进来，跳过
                        return False
                    break
            remaining = tuple(x for j, x in enumerate(rest) if j not in taken)
            return solve(remaining, people - 1)   # 这个人的组合定型，剩下的交给下一个人

        ok = fill(0, limit - first, set())
        if not ok:
            failed.add((items, people))
        return ok

    return solve(tuple(work), n)

lo, hi = max(work[0], (sum(work) + n - 1) // n), sum(work)   # 下界 = max(最大单件, 平均值上取整)，上界 = 全部给一个人
while lo < hi:
    mid = (lo + hi) // 2
    if check(mid):
        hi = mid                           # 可行 → 上限还能更小
    else:
        lo = mid + 1                       # 不可行 → 至少要比 mid 大
print(lo)

自测用例：题面示例（→ 28）、第 06 节的 8 7 6 5 / 2（→ 13）、第 07 节的 3 11 7 5 10 3 / 2（→ 20）和偶数构造输入 2 4 … 58 / 2（→ 436）；小规模输入可以再写一个「枚举每件归谁」的全枚举对拍。搜索最坏仍是指数级，M < 30 也不能保证快速完成。工作量相近、可选组合多时尤其要留意运行时间；先用小规模全枚举验证答案，再按题目的数据范围与时限检查性能。题目页参考题解使用更快的贪心，但它会在第 07 节的反例上给出偏大答案，不能作为精确搜索的正确性依据。

def lower_bound(nums, target):
    lo, hi = 0, len(nums)             # 半开区间 [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:       # mid 满足 → 答案在 mid 或左边
            hi = mid
        else:                         # mid 不满足 → 答案在右边
            lo = mid + 1
    return lo                         # 结束时 lo 左边全 < target，lo 及右边全 ≥ target

assert lower_bound([1, 3, 3, 5], 3) == 1
assert lower_bound([1, 3, 3, 5], 6) == 4     # 比所有数都大 → n
assert lower_bound([1, 3, 3, 5], 0) == 0     # 比所有数都小 → 0
assert lower_bound([], 7) == 0               # 空数组

def check(k, piles, h):
    hours = 0
    for p in piles:
        hours += (p + k - 1) // k     # 整数上取整
    return hours <= h

assert check(4, [3, 6, 7, 11], 8) is True    # 1+2+2+3 = 8
assert check(3, [3, 6, 7, 11], 8) is False   # 1+2+3+4 = 10
assert check(11, [3, 6, 7, 11], 4) is True   # 速度 = 最大堆：每棵 1 小时

七条断言覆盖：找到、越界（大 / 小）、空数组、可行、不可行、速度等于最大堆。