[JSOI2007] 建筑抢修

形式化题目

给定 $N$ 个任务，第 $i$ 个任务需运行 $t_i$ 时间，截止时间为 $d_i$ 。任务依次执行不可抢占，求最多有多少个任务能在其截止时间前完成。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 22;

struct Building {
    long long need_time;
    long long deadline;
};

int n;
Building buildings[MAXN];

bool cmp_building(const Building &a, const Building &b) {
    if (a.deadline != b.deadline) {
        return a.deadline < b.deadline;
    }
    return a.need_time < b.need_time;
}

bool check_subset(int mask) {
    vector<Building> chosen;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            chosen.push_back(buildings[i]);
        }
    }

    sort(chosen.begin(), chosen.end(), cmp_building);
    long long cur = 0;
    for (int i = 0; i < (int)chosen.size(); i++) {
        cur += chosen[i].need_time;
        if (cur > chosen[i].deadline) {
            return false;
        }
    }
    return true;
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> buildings[i].need_time >> buildings[i].deadline;
    }

    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (check_subset(mask)) {
            ans = max(ans, __builtin_popcount((unsigned)mask));
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力枚举所有子集，对每个子集按截止时间排序后检查可行性。瓶颈是 $O(2^n)$ ，仅适用于 $n \le 20$ 的小数据。

为什么按截止时间排序是最优顺序？

假设选定了一组任务要完成，怎样安排顺序最不容易超时？直觉上截止时间早的先做。严格证明用交换论证：若存在任务 A、B 满足 $d_A < d_B$ 但 B 排在 A 前面，交换它们——A 更早完成、B 推迟不超时，因此不劣。由此按截止时间升序排列对任何固定任务子集都是最优顺序。

这个观察的意义：一旦确定了顺序，问题就变成了"从左到右，选不选当前任务"的决策问题。

装不下时，删掉耗时最长的那个——为什么对？

处理到第 $i$ 个任务，已选集合总耗时为 $T$ 。若 $T + t_i \le d_i$ ，选它；否则装不下，删掉已选中耗时最长的任务。理由：剩余任务数不变，但总耗时减少最多，给后续留下最大时间余量。

严格证明用归纳不变量：

处理完前 $k$ 个任务（按截止时间排序）后，算法维护的集合 $S_k$ 是 $\{1..k\}$ 的所有可行子集中数量最大的，且在数量最大的所有可行子集中总耗时最小的。

情况 A： $T + t \le d$ 。 $S_{k+1} = S_k \cup \{k+1\}$ 。 $\{1..k+1\}$ 的任何可行子集限制到 $\{1..k\}$ 最多 $|S_k|$ 个，所以最多 $|S_k|+1$ 个。 $S_{k+1}$ 恰好达到。

情况 B： $T + t > d$ 。 从 $S_k \cup \{k+1\}$ 中去掉耗时最长的任务 $m$ 。假设存在可行子集 $O \subseteq \{1..k+1\}$ 且 $|O| = |S_k|+1$ 。 $O$ 必含 $k+1$ （否则 $|O| > |S_k|$ 与归纳假设矛盾）。于是 $O \setminus \{k+1\} \subseteq \{1..k\}$ 且 $|O \setminus \{k+1\}| = |S_k|$ 。由归纳假设 $T \le \text{total}(O \setminus \{k+1\})$ ，又 $O$ 可行要求 $\text{total}(O \setminus \{k+1\}) + t \le d$ ，得 $T + t \le d$ ，与 $T + t > d$ 矛盾。因此 $|S_k|$ 就是 $\{1..k+1\}$ 的最大可行子集数量。总耗时最小性同理可证。

为什么超时后只需删一次，不用循环删到不超时？

因为一次删除必然足够，第二次永远不会发生：

处理第 $i$ 个任务前，已选集合是可行的，即总耗时 $T \le d_{i-1}$ （或之前的某个截止时间）。
按截止时间升序处理，所以 $d_{i-1} \le d_i$ ，于是 $T \le d_i$ 。
加入 $t_i$ 后可能超时，但弹出的 $m$ 是堆里最大的工期，而堆里包含 $t_i$ ，所以 $m \ge t_i$ 。
删掉后总耗时变为 $T + t_i - m \le T \le d_i$ ，一次删除就回到不超时。

C++ 版使用 STL priority_queue（默认大根堆）维护已选任务中最长的工期，堆顶就是需要替换的目标。

如果想对齐 rbook 的 heap 模板，也可以手写 up/down 完成同样的操作，见 main2.cpp。

Python 知识

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;

struct Building {
    long long need_time;
    long long deadline;
};

int n;
Building buildings[MAXN];

bool cmp_building(const Building &a, const Building &b) {
    if (a.deadline != b.deadline) {
        return a.deadline < b.deadline;
    }
    return a.need_time < b.need_time;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> buildings[i].need_time >> buildings[i].deadline;
    }

    sort(buildings + 1, buildings + n + 1, cmp_building);

    // 大根堆：priority_queue 默认堆顶最大，堆顶就是已选任务中最长的工期。
    priority_queue<long long> selected;
    long long total_time = 0; // 已选任务的总工期

    for (int i = 1; i <= n; i++) {
        total_time += buildings[i].need_time;
        selected.push(buildings[i].need_time);

        // 当前任务超时：扔掉已选任务中工期最长的，给后续留余量。
        if (total_time > buildings[i].deadline) {
            total_time -= selected.top();
            selected.pop();
        }
    }

    cout << selected.size() << '\n';
    return 0;
}

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-10 17:19
 * update_at: 2026-08-10 17:19
 */
// main2.cpp：手写堆版本，风格对齐 rbook 的 heap 模板（h[0] 不使用，up/down 维护堆序）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;

struct Building {
    long long need_time;
    long long deadline;
};

int n;
Building buildings[MAXN];

// 最大堆：手写实现，风格对齐 rbook 的 heap 模板（h[0] 不使用）。
template <typename T>
struct MaxHeap {
    vector<T> h;

    MaxHeap() {
        h.push_back(T());
    }

    int size() const {
        return (int)h.size() - 1;
    }

    bool empty() const {
        return size() == 0;
    }

    T top() const {
        return h[1];
    }

    void up(int u) {
        while (u > 1 && h[u] > h[u / 2]) {
            swap(h[u], h[u / 2]);
            u /= 2;
        }
    }

    void down(int u) {
        while (true) {
            int best = u;
            int left = u * 2;
            int right = u * 2 + 1;

            if (left <= size() && h[left] > h[best]) best = left;
            if (right <= size() && h[right] > h[best]) best = right;
            if (best == u) break;

            swap(h[u], h[best]);
            u = best;
        }
    }

    void push(const T &x) {
        h.push_back(x);
        up(size());
    }

    void pop() {
        if (empty()) return;
        h[1] = h.back();
        h.pop_back();
        if (!empty()) down(1);
    }
};

bool cmp_building(const Building &a, const Building &b) {
    if (a.deadline != b.deadline) {
        return a.deadline < b.deadline;
    }
    return a.need_time < b.need_time;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> buildings[i].need_time >> buildings[i].deadline;
    }

    sort(buildings + 1, buildings + n + 1, cmp_building);

    MaxHeap<long long> selected; // 已选任务的工期，堆顶是最大的那个
    long long total_time = 0;    // 已选任务的总工期

    for (int i = 1; i <= n; i++) {
        total_time += buildings[i].need_time;
        selected.push(buildings[i].need_time);

        // 当前任务超时：扔掉已选任务中工期最长的，给后续留余量。
        if (total_time > buildings[i].deadline) {
            total_time -= selected.top();
            selected.pop();
        }
    }

    cout << selected.size() << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import 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(n\log n)$ ，空间 $O(n)$ 。

总结

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