二分答案与贪心判定

import sys

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
t = [int(x) for x in data[2:2 + n]]


def check(limit):                                 # 每片耗时之和都不超过 limit 时，最少要切几片？≤ k 即可行
    pieces, cur = 1, 0
    for x in t:
        if x > limit:                             # 单条就超限：怎么切都不行
            return False
        if cur + x > limit:                       # 放不进当前片：开新片
            pieces += 1
            cur = x
        else:
            cur += x
    return pieces <= k                            # 片数少于 k 也可行：再切开不会增大最大值


lo, hi = max(t), sum(t)                           # 下界：最长的单条；上界：全部放一片
while lo < hi:                                    # 求最小可行值：左中点，可行则 hi = mid
    mid = (lo + hi) // 2
    if check(mid):
        hi = mid
    else:
        lo = mid + 1
print(lo)

用两组题面示例（18、22）、练习 2 的 k = 3（14）和 3 3 / 3 1 4（4）核对；n = 2000 时二分 + O(n) 判定在时限内。

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]


def check(length):                                # 把所有短于 length 的木板补到 length，木料够不够
    need = 0
    for x in a:
        if x < length:
            need += length - x
    return need <= m


lo, hi = min(a), min(a) + m                       # 下界：不补也可行；上界：全部木料补最短那块
while lo < hi:                                    # 求最大可行值：右中点，可行则 lo = mid
    mid = (lo + hi + 1) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid - 1
print(lo)

用两组题面示例 5 / 4 和第 04 节的 [3,5,6]、m = 4 → 6 核对；题目页参考题解是逐级补齐的模拟写法，结果相同。

import sys
from collections import deque

data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
grid = [[int(data[2 + i * C + j]) for j in range(C)] for i in range(R)]


def check(level):                                 # 只走信号 ≥ level 的格子，起点能否到终点
    if grid[0][0] < level or grid[R - 1][C - 1] < level:
        return False
    seen = [[False] * C for _ in range(R)]
    seen[0][0] = True
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        if (x, y) == (R - 1, C - 1):
            return True
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < R and 0 <= ny < C and not seen[nx][ny] and grid[nx][ny] >= level:
                seen[nx][ny] = True
                q.append((nx, ny))
    return False


lo, hi = min(min(row) for row in grid), min(grid[0][0], grid[R - 1][C - 1])   # 答案不超过起点与终点中较小的那个
while lo < hi:                                    # 求最大可行值：右中点，可行则 lo = mid
    mid = (lo + hi + 1) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid - 1
print(lo)

用题面示例 → 4 和第 07 节的 5×3 网格 → 9 核对。判定用 BFS，一次 O(RC)。

def min_max_piece(t, k):
    def check(limit):                        # 每片和 ≤ limit 时最少切几片，≤ k 即可行
        pieces, cur = 1, 0
        for x in t:
            if x > limit:
                return False
            if cur + x > limit:
                pieces += 1
                cur = x
            else:
                cur += x
        return pieces <= k

    lo, hi = max(t), sum(t)
    while lo < hi:                           # 求最小可行值：左中点 + 可行则 hi = mid
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

assert min_max_piece([7, 2, 5, 10, 8], 2) == 18     # AI018 题面示例 1（第 05 节表）
assert min_max_piece([7, 2, 5, 10, 8], 3) == 14     # 练习 2：k = 3
assert min_max_piece([5, 9, 1, 7], 1) == 22         # 只切一片 = 总和
assert min_max_piece([3, 1, 4], 3) == 4             # k = n：答案是最大单条
assert min_max_piece([1, 1, 100, 1], 2) == 101      # 下界 max(t) 的意义
assert min_max_piece([0, 0, 7, 0, 3], 2) == 7       # 含 0

先单独跑 check(17)、check(18) 再跑二分：断言全过时，判定与收缩两部分都对。

def max_min_board(a, m):
    def check(length):                       # 把所有短于 length 的木板补到 length，木料够不够
        need = 0
        for x in a:
            if x < length:
                need += length - x
        return need <= m

    lo, hi = min(a), min(a) + m              # 上界：全部木料补最短那块
    while lo < hi:                           # 求最大可行值：右中点 + 可行则 lo = mid
        mid = (lo + hi + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

assert max_min_board([4, 5, 3, 5, 5], 3) == 5       # P2497 题面示例 1
assert max_min_board([4, 5, 3, 5, 5], 2) == 4       # 题面示例 2
assert max_min_board([3, 5, 6], 4) == 6             # 第 04 节表
assert max_min_board([1, 2], 100) == 51             # 上界取 max(a) 会得 2

两处相反：中点 (lo + hi + 1) // 2，可行时 lo = mid。