BISHI50　[JSOI2007]建筑抢修¶

中等通过率 37.2%python3样例通过牛客 AC

牛客原题　源码

讲解章节：优先队列与堆、贪心

一句话

单机调度，每个任务耗时 t_i、截止 d_i，最多完成几个。

解题思路¶

这题考什么¶

经典的「反悔贪心 / 带截止期的单机调度」：

把所有建筑按截止时间 d 升序排序；
依次尝试加入：cur += t_i，把 t_i 压进一个大根堆；
如果 cur > d_i（这一批修不完了），就从堆里弹出耗时最长的那个任务不修了，cur 减去它。因为放弃一个任务只会让完成数 -1，而放弃最耗时的那个能给后面腾出最多时间，是最划算的反悔。

循环结束后堆的大小就是答案。

为什么按 d 排序：若某个可行解里存在 d 大的排在 d 小的前面，交换这两个任务不会让任何一个超时（经典交换论证），所以总存在一个按 d 升序执行的最优解。

验算样例（按 d 排序后是 (100,200),(1000,1250),(200,1300),(2000,3200)）： cur=100<=200 ✓；cur=1100<=1250 ✓；cur=1300<=1300 ✓； cur=3300>3200，弹出最大的 2000 -> cur=1300，堆里剩 3 个 -> 答案 3 ✓。

数据规模与复杂度¶

n <= 1.5e5，t,d <= 2e9（超过 32 位有符号范围的上界附近，C/C++ 要 long long）。排序 O(n log n) + 堆操作 O(n log n)，总时间约 3e6 次基本操作。 Python 的 heapq 是小根堆，存 -t 即可当大根堆用。

坑在哪¶

判定是 cur <= d_i（在 d_i 秒内完成，取等号也算成功），样例里恰好有一个 1300 == 1300 的边界，写成 < 就会少算一个；
只能在超时的时候弹，而且弹完之后不用回退指针 —— 当前任务已经在堆里，弹出的可能正是它自己（说明它太长，不如不修）；
排序键只用 d，不能用 t 或 d-t；
输出的是「最多能修好的数量」，不是时间；
反悔贪心（regret greedy，即「先接下来、发现装不下再退掉最差的一个」）与「先排序再一次性挑选」的区别在于：它允许推翻此前的决定，所以能在一次扫描里同时兼顾「按截止期推进」和「总耗时最小」。

堆的用法见 35-优先队列与堆，贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI50.py
import sys
from heapq import heappush, heappop


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    jobs = []
    p = 1                             # 游标：n 行数据，每行 (t_i, d_i) 两个整数
    for _ in range(n):
        t = int(data[p]); d = int(data[p + 1]); p += 2
        jobs.append((d, t))           # 存成 (d, t)，让默认元组排序直接按 d 排
    jobs.sort()                       # 按截止时间升序

    heap = []                         # 大根堆（存负数）：已接下的任务耗时
    cur = 0                           # 已接下的任务总耗时 = 当前完工时刻
    for d, t in jobs:
        # 先无条件接下这个任务，超时了再回头反悔
        cur += t
        heappush(heap, -t)
        if cur > d:                   # 修不完了，反悔掉最耗时的那个
            cur += heappop(heap)      # heap 里是负数，加上等于减去耗时
    print(len(heap))                  # 堆里剩几个任务，就修好了几座建筑


main()

BISHI50 [JSOI2007]建筑抢修¶