题解 | #[JSOI2007]建筑抢修#

题目链接

BISHI50 [JSOI2007]建筑抢修

题目描述

有 $n$ 座受损建筑。维修工可忽略移动时间，但同一时刻只能维修一座建筑。维修第 $i$ 座建筑需要时间 $t_i$ ，且必须在截至时间 $d_i$ 之前全部完成，否则报废。请安排维修顺序，使最终在各自时限内完成的建筑数量最大，并输出最大数量。

解题思路

贪心 + 优先队列（最大堆）：按截止时间从小到大排序所有建筑对 $(t_i, d_i)$ 。维护当前选择集合的总工时 $T$ 与一个存放所选建筑工时的最大堆。
- 依次处理每个建筑：将 $t_i$ 加入集合（入堆），并令 $T \leftarrow T + t_i$ 。
- 若 $T > d_i$ ，说明在当前截止时间 $d_i$ 前无法完成所有已选建筑，应当删除集合中工时最大的那座（从最大堆弹出），并从 $T$ 中减去该最大工时。这样最不“友好”的建筑被移除，留下更有利于容纳更多数量的集合。
- 遍历结束后，堆中元素个数即为最多可完成的建筑数量。
正确性（交换论证）：在固定前缀的情况下，若总工时超限，移除当前集合中 $t$ 最大的任务，得到的集合不劣于移除任何其他任务的选择，因而贪心选择成立。
复杂度：排序 $\mathcal{O}(n\log n)$ ，每个元素至多入堆、出堆一次，总计 $\mathcal{O}(n\log n)$ ；空间 $\mathcal{O}(n)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long,long long>> a(n); // (d_i 排序用, t_i)
    for (int i = 0; i < n; ++i) {
        long long t, d; cin >> t >> d;
        a[i] = {d, t};
    }
    sort(a.begin(), a.end()); // 按 d_i 升序

    priority_queue<long long> pq; // 最大堆，存当前选中的 t_i
    long long T = 0; // 当前总工时
    for (auto &e : a) {
        long long d = e.first, t = e.second;
        pq.push(t);
        T += t;
        if (T > d) { // 超过当前截止时间，移除工时最大者
            T -= pq.top();
            pq.pop();
        }
    }
    cout << (int)pq.size() << '\n';
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] a = new long[n][2]; // a[i][0]=d_i, a[i][1]=t_i
        for (int i = 0; i < n; i++) {
            long t = sc.nextLong();
            long d = sc.nextLong();
            a[i][0] = d; a[i][1] = t;
        }
        Arrays.sort(a, (x, y) -> Long.compare(x[0], y[0]));

        PriorityQueue<Long> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 最大堆
        long T = 0;
        for (int i = 0; i < n; i++) {
            long d = a[i][0], t = a[i][1];
            pq.add(t);
            T += t;
            if (T > d) {
                T -= pq.poll(); // 移除当前集合中最大的 t
            }
        }
        System.out.println(pq.size());
    }
}

n = int(input())
tasks = []
for _ in range(n):
    t, d = map(int, input().split())
    tasks.append((d, t))  # (deadline, time)

tasks.sort()

import heapq

pq = []            # 最大堆用负值模拟
total = 0          # 当前总工时
for d, t in tasks:
    heapq.heappush(pq, -t)
    total += t
    if total > d:
        total += heapq.heappop(pq)  # 弹出的是 -max_t，相当于 total -= max_t

print(len(pq))

算法及复杂度

算法：按 $d_i$ 升序排序，维护最大堆与总工时 $T$ ，当 $T>d_i$ 时移除当前集合中最大的 $t$ ，最终堆大小即答案。
时间复杂度： $\mathcal{O}(n\log n)$ 。
空间复杂度： $\mathcal{O}(n)$ 。