[USACO09OPEN] Work Scheduling G

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

按截止时间排序，若已选工作数超过当前截止时间，就用小根堆删掉利润最小的工作。

OJ: luogu

题目 ID: P2949

难度:普及+/提高

标签:贪心堆反悔贪心排序

日期: 2026-06-22 20:53

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 n 个工作，每个工作都需要 1 个单位时间。工作 i 有截止时间 d_i 和利润 p_i，若能在截止时间前完成，就能得到利润。

求最大总利润。

思路

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

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 22;

struct Job {
    int deadline;
    long long profit;
};

int n;
Job jobs[MAXN];

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

    sort(deadlines.begin(), deadlines.end());
    for (int i = 0; i < (int)deadlines.size(); i++) {
        int finish_time = i + 1;
        if (finish_time > deadlines[i]) {
            return false;
        }
    }
    return true;
}

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

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

    long long ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (!check_subset(mask)) {
            continue;
        }
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                sum += jobs[i].profit;
            }
        }
        ans = max(ans, sum);
    }

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

暴力会枚举所有工作子集，检查是否能按时完成。这个做法只能用于小数据。

因为每个工作耗时都是 1，按截止时间从小到大处理工作时，如果当前截止时间是 d，那么在目前这些工作中最多只能选择 d 个。

每个工作先加入选择集合。如果选择数量超过当前截止时间，就必须删掉一个已选工作。为了让利润尽量大，应该删掉利润最小的那个。

用小根堆维护当前已选工作的利润即可。

代码

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

const int MAXN = 100005;

struct Job {
    long long deadline;
    long long profit;
};

int n;
Job jobs[MAXN];

bool cmp_job(const Job &a, const Job &b) {
    if (a.deadline != b.deadline) {
        return a.deadline < b.deadline;
    }
    return a.profit > b.profit;
}

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

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

    sort(jobs + 1, jobs + n + 1, cmp_job);

    priority_queue<long long, vector<long long>, greater<long long> > selected;
    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        selected.push(jobs[i].profit);
        ans += jobs[i].profit;

        if ((long long)selected.size() > jobs[i].deadline) {
            ans -= selected.top();
            selected.pop();
        }
    }

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

复杂度

排序和堆操作都是：

text
O(n log n)

空间复杂度为 O(n)O(n)。

总结

本题和建筑抢修类似，都是反悔贪心。

区别在于本题所有工作耗时都是 1，所以超限条件是“已选数量超过截止时间”；反悔时删掉的是利润最小的工作。