[JSOI2007] 建筑抢修

GitHub跳转原题关系图返回列表

按截止时间扫描，最大堆维护已选工期；超时则用更短任务替换最长任务。

OJ: luogu

题目 ID: P4053

难度:普及+/提高

标签:贪心最大堆调度python

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

单机任务有工期和截止时间，求最多能按时完成多少个。

思路

按截止时间排序。当前任务能按时完成就选择；否则若它比已选任务中最长工期更短，用它替换最长任务。任务数不变但总耗时减小，为后续留下更多余量。

Python 知识

  • sorted(..., key=lambda item: item[1]) 明确按截止时间排序。
  • 负工期最大堆让 -heap[0] 是已选最长任务。
  • heapreplace 一次替换堆顶，并返回被替换负值用于修正总时间。

代码

python
import heapq
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
buildings = sorted(((next(data), next(data)) for _ in range(next(data))),
                   key=lambda item: item[1])
chosen = []
elapsed = 0

for duration, deadline in buildings:
    if elapsed + duration <= deadline:
        elapsed += duration
        heapq.heappush(chosen, -duration)
    elif chosen and -chosen[0] > duration:
        elapsed += duration + heapq.heapreplace(chosen, -duration)

print(len(chosen))

复杂度

排序和堆操作总计 O(nlog⁡n)O(n\log n)，空间 O(n)O(n)。

总结

以截止时间推进时，固定已选数量下总工期越小越优，因此超时应淘汰最长任务。