奶牛Bessie工作调度：如何最大化完成工作数量？

这个问题是一个经典的任务调度问题，目标是选择尽可能多的工作，使得每个工作都能在截止时间前开始并完成。 我们可以将工作按照截止时间 \( 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; } ``` ######[AI问答 | 494点数解答 | 2026-01-18 12:55:29]