游戏通关

GitHub跳转原题关系图返回列表

使用按截止时间排序配合小根堆反悔贪心算法来求解最大奖励任务调度问题。

OJ: roj

题目 ID: 5008

难度:普及

标签:贪心优先队列反悔贪心

创建: 2026-10-08 09:07

更新: 2026-10-08 09:07

形式化题目

有 NN 个任务,每个任务有一个完成最后期限 TiT_i 以及完成该任务后的奖励 WiW_i。每个任务恰好需要一个单位的时间来完成。可以在任意顺序下执行任务。初始时间为 00。求在这个条件下,能获得的最大总奖励。

正解

思路

这是一个典型的带截止时间和奖励的任务调度问题,可以用反悔贪心的策略来解决。

  1. 贪心排序: 将所有任务按照最后期限 TiT_i 从小到大排序。这是因为期限早的任务应该优先考虑,否则就可能过期。

  2. 维护当前选择: 使用一个小根堆(优先队列)来维护当前已经被选中去执行的任务的奖励 WW。堆中元素的个数即表示已经安排了多少个任务,也就对应了当前的消耗时间(因为每个任务耗时1)。

  3. 反悔机制: 对于排序后的每个任务:

    • 如果当前堆的大小(已选任务数)小于该任务的最后期限 TiT_i,说明时间上还允许完成该任务,那么直接将其奖励加入堆中。
    • 如果堆的大小等于该任务的最后期限 TiT_i(不能直接加入),但该任务的奖励比堆顶的奖励(即当前已选任务中奖励最小的那个)还要大,此时我们就可以选择放弃堆顶的那个任务,改为完成当前这个奖励更大的任务。所以我们将堆顶弹出,将当前任务奖励压入堆中。这本质上就是一种“反悔”。

最后,堆中所有任务的奖励之和,就是能获得的最大总奖励。

代码

python
import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    
    tasks = []
    idx = 1
    for _ in range(n):
        t = int(input_data[idx])
        w = int(input_data[idx+1])
        tasks.append((t, w))
        idx += 2
        
    tasks.sort(key=lambda x: (x[0], -x[1]))
    
    pq = []
    
    for t, w in tasks:
        if len(pq) < t:
            heapq.heappush(pq, w)
        elif pq and pq[0] < w:
            heapq.heappop(pq)
            heapq.heappush(pq, w)
            
    print(sum(pq))

if __name__ == '__main__':
    solve()
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Task {
    int t, w;
    bool operator<(const Task& other) const {
        if (t != other.t)
            return t < other.t;
        return w > other.w;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<Task> tasks(n);
    for (int i = 0; i < n; ++i) {
        cin >> tasks[i].t >> tasks[i].w;
    }

    sort(tasks.begin(), tasks.end());

    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < n; ++i) {
        if (pq.size() < tasks[i].t) {
            pq.push(tasks[i].w);
        } else if (!pq.empty() && pq.top() < tasks[i].w) {
            pq.pop();
            pq.push(tasks[i].w);
        }
    }

    long long max_reward = 0;
    while (!pq.empty()) {
        max_reward += pq.top();
        pq.pop();
    }

    cout << max_reward << "\n";

    return 0;
}

复杂度

  • 时间复杂度:
    • 排序任务的时间为 O(Nlog⁡N)O(N \log N)。
    • 遍历所有任务,每个任务最坏情况下可能需要进行一次堆的插入和弹出操作,堆的大小最大为 NN,所以这部分时间也为 O(Nlog⁡N)O(N \log N)。
    • 总体时间复杂度为 O(Nlog⁡N)O(N \log N),这对于 N≤200,000N \le 200,000 的数据规模是完全可以在规定时间内跑完的。
  • 空间复杂度:
    • 存储 NN 个任务所需的数组/列表占 O(N)O(N)。
    • 维护的小根堆大小最大也可能达到 O(N)O(N)。
    • 总体空间复杂度为 O(N)O(N)。

总结

本题利用贪心配合优先队列(小根堆)进行任务调度是一个非常经典的解法。将“优先满足截止期限早的任务”与“在满载时替换掉价值最低的任务以获得更高收益(反悔)”结合,不仅思维上十分巧妙,还能保证时间复杂度在一个非常优秀的水平(O(Nlog⁡N)O(N \log N))。

注:本题素材源中包含数据生成脚本 data.py 和 gen.*,说明测试数据是自造的。