形式化题目

有 $n$ 个商品, 第 $i$ 个商品有利润 $p_i$ 和截止日期 $d_i$. 每个商品卖出需要恰好一天, 一天只能卖一个商品, 且第 $i$ 个商品必须在第 $d_i$ 天结束前卖出 (从第 $1$ 天开始计).

从所有商品中选出若干件并排出一个出售顺序, 使每一件都赶上自己的截止日期, 求能拿到的最大总利润. 卖不掉的商品直接丢弃.

解法总览

这题的关键是"一天只能卖一件"和"每件有个截止日期"这两个条件互相纠缠. 直觉上应该先卖值钱的, 但值钱的商品又未必赶得上; 或者先卖急的, 可急的未必值钱.

解法一按截止日期排序, 边加边用堆反悔; 解法二按利润排序, 直接抢占最晚空位. 两者都把二维的"利润 + 时间"压成了一维的一条排序主线, 复杂度同为 $O(n\log n)$, 但思路方向相反.

正式主解是解法一 main.cpp: 它不依赖截止日期的上界, 也不需要对并查集做初始化, 写起来更短. 解法二的价值在于"占用一天就把这一天并到前一天"这个技巧, 是并查集维护区间空位的经典用法.

解法一: 反悔贪心 + 优先队列

适用范围

$0\leqslant n\leqslant 10^4$, $1\leqslant p_i,d_i\leqslant 10^4$. 复杂度 $O(n\log n)$, 与截止日期的大小无关.

思路

先按截止日期从小到大排序. 这样处理到某个商品时, 之前处理过的所有商品截止日期都不比它晚.

维护一个"购物车", 里面放当前决定要卖的商品. 只关心这些商品的利润, 用一个小顶堆存, 堆顶就是车里最不值钱的那件.

设当前商品的截止日期是 $d$, 利润是 $p$, 车里有 $m$ 件:

• $m<d$: 还有空位, 直接卖.
• $m=d$: 从第 $1$ 天到第 $d$ 天已经排满. 此时只有一种值得做的事 — 如果 $p$ 比车里最不值钱的那件还大, 就把那件扔掉, 换成 $p$. 其余情况什么都不做.

第二种情况就是"反悔": 前面因为不知道后面有更好的商品, 可能选了一件凑合的; 现在知道了, 就退掉它.

为什么 $m$ 只会等于 $d$ 而不会超过? 因为只在 $m<d$ 时无条件加入, 加入后 $m\leqslant d$; 替换操作不改变 $m$. 所以车里始终有 $m\leqslant d$, 永远有位置放.

用题面第一组数据走一遍, 商品按截止日期排好是 $(10,1),(30,1),(50,2),(20,2)$:

最后总利润 $30+50=80$, 正是题面给的答案. 注意第二步: 如果不用反悔, 直接把 $(30,1)$ 丢掉, 后面就会少赚 $20$.

为什么这样选是对的

要证明的是: 处理完前 $i$ 个商品后, 车里装的就是这 $i$ 个商品的最优可行子集. 对 $i$ 归纳, 只需看清新来的第 $i+1$ 件商品 (截止日期 $d$, 利润 $p$, 且 $d$ 是已处理商品中最大的) 的两种情形:

• 情形 $m<d$: 加入不破坏可行性. 车里原有商品的截止日期都不超过 $d$; 把新商品排在最后卖, 它占用第 $m+1$ 天, 而 $m+1\leqslant d$, 赶得上. 又因为 $p>0$, 所以最优解一定拿它, 最优值增加 $p$.
• 情形 $m=d$: 替换是安全且必要的. 设原最优集为 $S$, $|S|=d$.
  • 安全: 换掉车里最差的 $Y$ (利润 $\leqslant p$), 换成 $X$. 换完集合大小仍是 $d$, 且 $X$ 的截止日期 $d$ 是当前最大的, 把 $X$ 排在最后, 它占第 $d$ 天, 满足 $d\geqslant d$; 其余商品的位置不动. 所以新集合仍然可行, 利润不降.
  • 必要: 前 $i+1$ 件商品里任何可行集大小都不超过 $d$, 而 $S$ 已经是满的 $d$ 件. 想腾出位置就必丢掉一件, 丢最便宜的损失最小.

两条合起来: 每一步都保持"当前最优", 处理完所有商品时车里的就是全局最优. $\square$

第三行的"$d$ 是当前最大"值得单独强调: 排序保证了这一点, 所以替换时把新商品放到时间轴最末尾一定合法, 不需要检查它与其它商品的相对顺序.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-27 21:05
 * update_at: 2026-10-27 21:05
 */
// main.cpp：反悔贪心 + 优先队列。按截止日期从小到大处理，维护一个"当前决定卖的商品"的小顶堆。
// 堆里攒够 d 件时，用利润更高的新商品替换掉堆里利润最低的那件。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10000 + 5;

// 一个商品：利润 p，截止日期 d
struct Item {
    int p;
    int d;
};

int n;
Item item[MAXN];

// 按截止日期从小到大排序
bool compare_by_deadline(const Item &a, const Item &b) {
    return a.d < b.d;
}

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

    // 本题是多组输入，读到 EOF 为止
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> item[i].p >> item[i].d;

        sort(item, item + n, compare_by_deadline);

        // cart 里存已选中商品的利润。用小顶堆放利润最低的那件，方便"反悔"时换掉它
        priority_queue<int, vector<int>, greater<int> > cart;
        for (int i = 0; i < n; i++) {
            if ((int)cart.size() < item[i].d) {
                cart.push(item[i].p); // 还有空位，直接卖
            } else if (!cart.empty() && item[i].p > cart.top()) {
                // 位置已经排满，但当前商品更值钱：扔掉最差的，换上它
                cart.pop();
                cart.push(item[i].p);
            }
        }

        ll answer = 0;
        while (!cart.empty()) {
            answer += cart.top();
            cart.pop();
        }
        cout << answer << '\n';
    }

    return 0;
}

复杂度

• 排序 $O(n\log n)$.
• 每件商品对堆做一次 $O(\log n)$ 的操作, 共 $O(n\log n)$.
• 总时间 $O(n\log n)$, 空间 $O(n)$.

空间与截止日期的大小无关, 这是它比解法二省心的地方.

解法二: 贪心 + 并查集

适用范围

同样的约束范围. 复杂度也是 $O(n\log n)$, 但并查集数组要开到 $\max d_i$, 本题即 $10^4$.

思路

换一个排序依据: 按利润从大到小处理. 值钱的商品优先, 这个方向很自然 — 但值钱的商品不一定能卖出去, 所以每件商品都要回答一个问题:

在我的截止日期之内, 还有哪一天是空的? 有的话, 挑最晚的那天.

为什么挑最晚? 因为越晚的日期越是"只有截止日期大的商品才能用", 把它留给别人反而是浪费; 而早的日子所有商品都能用, 应该尽量省着. 这条"往后靠"的直觉是解法二的灵魂.

逐个往左找空位太慢: 如果所有截止日期都是 $10^4$, 每件商品都可能往左扫 $10^4$ 步, 总计 $O(n\max d)$. 需要一种"找到某天之前最晚空位"的结构, 这正是并查集.

把每一天看作并查集里的一个点, 定义:

fa[i] 表示"第 $i$ 天或它之前, 最晚的可用日期".

• 初始 fa[i] = i, 表示每天都空着.
• 查询 find(d) 得到 r: 就是给截止日期为 $d$ 的商品安排的第 $r$ 天. 若 r = 0, 说明第 $1$ 天到第 $d$ 天全满, 这件商品只能放弃.
• 占用第 $r$ 天时执行 fa[r] = find(r-1): 把这一天并到前一天去. 下次再有人想用第 $r$ 天, 会直接被指到前一个空位.

路径压缩让连续被占的一段日子很快坍缩成一个点, 所以每次操作接近 $O(\alpha)$.

为什么这样选是对的

用交换论证. 按利润降序处理, 设在处理到商品 $X$ (利润 $p$, 截止日期 $d$) 时, find(d) 给出的最晚空位是 $r$:

• 若 $r=0$: 第 $1$ 到第 $d$ 天已被更值钱的商品占满. 任何一个包含 $X$ 的可行方案, 都必须在这 $d$ 天里腾出一格; 被腾出的那件利润 $\geqslant p$, 所以换进 $X$ 不会更好. 放弃 $X$ 不损失最优性.

• 若 $r>0$: 说明有方案把 $X$ 放在第 $r$ 天. 设某个最优方案 $O$ 没有选 $X$. 由于 $O$ 的所有商品利润都 $\leqslant p$ (它们是后面才处理的), 并且第 $r$ 天在 $O$ 里要么空着, 要么放着一件利润 $\leqslant p$ 的商品 $Y$:

  • 第 $r$ 天空着: 直接把 $X$ 放进去, 利润不减, 仍然可行.
  • 第 $r$ 天放着 $Y$: 用 $X$ 换掉 $Y$, 利润不减; 而 $Y$ 本来就在第 $r$ 天活着, 换成截止日期满足 $d\geqslant r$ 的 $X$ 仍然赶得上.

  两种子情形都能把 $O$ 改成包含 $X$ 且不亏的方案, 所以选 $X$ 不会失去最优性.

每条决策都不降低最优值, 累加起来就得到最优解. $\square$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-27 21:05
 * update_at: 2026-10-27 21:05
 */
// main2.cpp：贪心 + 并查集。按利润从大到小处理，每个商品都抢占"不晚于自己截止日期的最晚空位"。
// 并查集 fa[i] 表示「第 i 天或它之前最晚的可用日期」，占用一天就把 fa[r] 指向 r-1。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10000 + 5;

// 一个商品：利润 p，截止日期 d
struct Item {
    int p;
    int d;
};

int n;
Item item[MAXN];
int fa[MAXN]; // fa[i]：第 i 天或它之前最晚的可用日期

// 按利润从大到小排序
bool compare_by_profit(const Item &a, const Item &b) {
    return a.p > b.p;
}

// 并查集查找，带路径压缩。返回最近的可用的那一天，0 表示从 1 到 x 全被占满
int find_root(int x) {
    if (fa[x] == x) return x;
    fa[x] = find_root(fa[x]);
    return fa[x];
}

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

    // 本题是多组输入，读到 EOF 为止
    while (cin >> n) {
        int max_day = 0; // 本组数据出现的最大截止日期，用来决定并查集要初始化到哪一天
        for (int i = 0; i < n; i++) {
            cin >> item[i].p >> item[i].d;
            max_day = max(max_day, item[i].d);
        }

        sort(item, item + n, compare_by_profit);

        // 初始时每一天都可用，fa[i] = i 表示第 i 天就是它自己
        for (int i = 0; i <= max_day; i++) fa[i] = i;

        ll answer = 0;
        for (int i = 0; i < n; i++) {
            // 为这个商品找不晚于 item[i].d 的最晚空位
            int day = find_root(item[i].d);
            if (day > 0) {
                answer += item[i].p;
                fa[day] = find_root(day - 1); // 占用第 day 天，之后再来就往前找
            }
        }
        cout << answer << '\n';
    }

    return 0;
}

复杂度

• 排序 $O(n\log n)$.
• 每件商品一次 find 加一次合并, 摊还 $O(\alpha(\max d))$, 可视为常数.
• 总时间 $O(n\log n)$, 空间 $O(\max d)$.

复杂度对比

两种都是 $O(n\log n)$, 选哪个看习惯: 想少开数组、不关心 $d_i$ 多大就用解法一; 想体会"并查集维护连续被占区间"这个技巧就用解法二.

总结

这题有两个属性, 利润和时间, 同时考虑会很乱. 两个解法都是同一个动作:

挑一个属性排序, 把它固定下来, 只处理剩下的那个属性.

• 对时间排序 (解法一): 截止日期变成单调的, 于是"已选多少件"就能直接和当前截止日期比较, 冲突时用堆反悔.
• 对利润排序 (解法二): 利润变成单调的, 于是每件商品都值得抢, 剩下的问题只是"哪天有空", 用并查集回答.

两种排序各留下一个"待解决的困难": 前者是"选多了要不要退", 后者是"空位在哪". 堆和并查集正是为回答这两个问题而出现的.