轻重缓急（二）

题目描述

有 $N$ 件事，其中第 $i$ 件事需要 $T_i$ 分钟完成。一个人从 $0$ 时刻开始工作，每分钟只能做一件事，且一件事做到一半的时候，不能停下换另一件事。

每件事都有一个过期时间。第 $i$ 件事的最晚启动时间为 $D_i$，其含义是，第 $i$ 件事必须在 $0$ 时刻后的 $D_i$ 分钟内启动，否则就过期了。

请问，如何才能让尽量多的事情按期完成，输出可以完成的最大值。

输入格式

第一行：单个整数表示 $N$
第二行到第 $N+1$ 行：每行两个整数表示 $D_i$ 与 $T_i$

输出格式

单个整数：表示答案

数据范围

• 30% 的数据：$1\le N\le 20，0\le D_i\le 100，1\le T_i\le 100$
• 50% 的数据：$1\le N\le 1000$
• 100% 的数据：$1\le N\le 300000，0\le D_i\le 10^{18}，1\le T_i\le 10^{18}$

样例数据

样例1

输入：

2
5 10
6 9

输出：

1

说明：两件事只能做一件，开始任何一件都来不及做另一件事。

样例2

输入：

2
4 10
0 4

输出：

2

说明：先做第二件事，再做第一件事

---

题解

我来为你讲解这道题的解题思路和带注释的核心代码，只添加注释，不修改代码逻辑。

解题思路

这道题的核心是贪心算法 + 大根堆，目标是选择最多的任务完成，满足任务启动时间限制：

1. 核心规则：任务 $i$ 必须在 $D_i$ 时间前启动，且任务不可中断，总耗时为已选任务的时间和。
2. 排序策略：将所有任务按照 完成截止时间（D_i + T_i） 从小到大排序，优先处理能更早完成的任务。
3. 贪心选择：用大根堆维护已选任务的耗时，累加总耗时：
   • 若当前任务能满足启动时间要求，直接加入，计数+1；
   • 若不满足，替换掉堆中耗时最长的任务，减少总耗时，保证能选更多任务。

带注释的完整代码

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

// 任务总数，数据范围最大3e5
int n;
// 定义任务结构体，存储最晚启动时间d和耗时t，使用long long避免溢出
struct node {
    long long d, t;
};
// 存储所有任务，数组大小适配最大数据范围
node a[300005];
// 大根堆：存储已选任务的耗时，用于快速取出耗时最长的任务
priority_queue<long long> pq;
// sum：已选任务的总耗时
long long sum = 0;
// ans：最终能完成的最大任务数
int ans = 0;

// 排序规则：按 任务完成截止时间(d+t) 升序排列
bool cmp(node x, node y) {
    return x.d + x.t < y.d + y.t;
}

int main() {
    // 加速输入输出，应对大数据量
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 输入任务数量
    cin >> n;
    // 输入每个任务的 最晚启动时间d 和 耗时t
    for (int i = 1; i <= n; i++) {
        cin >> a[i].d >> a[i].t;
    }

    // 按照排序规则对任务排序
    sort(a + 1, a + n + 1, cmp);

    // 遍历每一个任务
    for (int i = 1; i <= n; i++) {
        // 先将当前任务的耗时加入大根堆
        pq.push(a[i].t);

        // 判断：当前总耗时 ≤ 任务最晚启动时间，说明可以启动该任务
        if (a[i].d >= sum) {
            // 累加任务耗时
            sum += a[i].t;
            // 完成任务数+1
            ans++;
        }
        // 不满足启动条件：替换掉耗时最长的任务，优化总耗时
        else {
            // 减去堆中最长的耗时
            sum -= pq.top();
            // 加上当前任务的耗时
            sum += a[i].t;
            // 弹出堆中最长耗时的任务
            pq.pop();
        }
    }

    // 输出最大可完成任务数
    cout << ans;
    return 0;
}

代码核心逻辑总结

1. 排序：按任务完成截止时间（D+T）从小到大排序，保证优先处理更紧急的任务；
2. 堆维护：用大根堆记录已选任务的耗时，实时调整总耗时；
3. 贪心替换：当新任务无法加入时，替换掉耗时最长的任务，用更小的总耗时容纳更多任务；
4. 复杂度：排序 $O(n\log n)$ + 堆操作 $O(n\log n)$，完美适配 $3\times 10^5$ 的大数据范围。