奶牛 Bessie 有 𝑁 （ 1 ≤ 𝑁 ≤ 2 ⋅ 10 5 ）个工作需要你去完成。第 𝑖 个工作，如果你选择完成它，必须在时刻 𝑠 𝑖 或之前开始，花费 𝑡 𝑖 时间才能完成（ 0 ≤ 𝑠 𝑖 ≤ 10 18 , 1 ≤ 𝑡 𝑖 ≤ 10 18 ）。 你可以完成的工作的最大数量是多少？时间从时刻 0 开始，并且一旦你开始一个工作，你必须一直工作直到完成，而不能在此期间开始完成其他工作。 输入 输入的第一行包含 𝑇 ，为测试用例的数量（ 1 ≤ 𝑇 ≤ 10 ）。每个测试用例的格式如下。 第一行包含 𝑁 。 以下 𝑁 行，每行包含两个整数 𝑠 𝑖 和 𝑡 𝑖 。第 𝑖 + 1 行为第 𝑖 个工作的信息。 输入保证所有测试用例的 𝑁 之和不超过 3 ⋅ 10 5 。 输出 对于每个测试用例输出一行，包含你可以完成的工作的最大数量。 样例输入 复制 3 2 1 4 1 2 2 2 3 1 2 3 1 4 2 3 1 2 样例输出 复制 1 2 2 提示 ## 提示 对于第一个测试用例，你

这个问题是一个经典的任务调度问题，目标是选择尽可能多的工作，使得每个工作都能在截止时间前开始并完成。 我们可以将工作按照截止时间 \( s_i \) 排序，然后使用一个优先队列（大根堆）来维护已选择的工作的耗时。 算法思路： 1. 将所有工作按 \( s_i \) 从小到大排序。 2. 遍历每个工作： - 将当前工作加入已选集合（将 \( t_i \) 加入优先队列，并累加总耗时 `sum_t`）。 - 如果 `sum_t > s_i`，说明当前已选工作无法全部在截止时间前完成，则移除耗时最长的工作（优先队列中最大的 \( t \)），并更新 `sum_t`。 3. 最终优先队列的大小就是能完成的最大工作数。 时间复杂度： 排序 \( O(N \log N) \)，每个工作最多一次入堆和出堆，也是 \( O(N \log N) \)，总复杂度 \( O(N \log N) \)，可以处理 \( N \leq 2\times 10^5 \) 的数据。 C++ 实现： ```cpp #include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int N; cin >> N; vector<pair<long long, long long>> jobs(N); for (int i = 0; i < N; i++) { cin >> jobs[i].first >> jobs[i].second; } // 按 s_i 排序 sort(jobs.begin(), jobs.end()); priority_queue<long long> pq; // 大根堆，存放已选工作的耗时 long long sum_t = 0; for (auto& job : jobs) { long long s = job.first, t = job.second; pq.push(t); sum_t += t; if (sum_t > s) { // 移除耗时最长的工作 sum_t -= pq.top(); pq.pop(); } } cout << pq.size() << "\n"; } return 0; } ``` [2026-01-18 12:55:29 | AI问答 | 494点数解答]