形式化题目

给定 $N$ 件商品，第 $i$ 件有正利润 $p_i$ 和过期时间 $d_i$。每天最多出售一件商品，且第 $i$ 件只能在第 $1, 2, \ldots, d_i$ 天中的某一天出售，过期后不能再卖。

求一个商品子集 $S$ 与一个单射的出售日安排 $t: S \to \mathbb{Z}_{>0}$，满足 $t_i \leqslant d_i$，使 $\sum_{i \in S} p_i$ 最大。

按题面样例 1，$(p,d)$ 为 $(50,2), (10,1), (20,2), (30,1)$。两件 $d = 1$ 的商品（利润 10 与 30）互斥，第 1 天只能留一件；两件 $d = 2$ 的商品（利润 50 与 20）可以在第 1、2 天各占一天。因此最优是“利润 30 占第 1 天，利润 50 占第 2 天”，收益 $80$；换成 $50 + 20 = 70$ 或 $20 + 30 = 50$ 都更差。

正解

思路

先明确可行性判据。 把候选子集 $S$ 的过期时间升序排成 $d_{(1)} \leqslant \cdots \leqslant d_{(k)}$，则 $S$ 可以安排出售日，当且仅当

必要性：前 $j$ 小的过期时间对应的 $j$ 件商品只能占用第 $1 \ldots d_{(j)}$ 天，而 $j$ 个互不相同的正整数必须落在 $\geqslant j$ 的范围里。充分性：把第 $j$ 小的那件安排在第 $j$ 天即可。这条判据把“怎么排期”从问题里消掉了：一件商品能不能卖出去，只取决于它和同伴们的过期时间分布。

朴素做法一：把时间摊成背包。 令 $f[d]$ 表示“只考虑第 $1 \ldots d$ 天”能取得的最大收益，对每件商品做一次选 / 不选的 0/1 背包转移。时间 $O(N \cdot \max d)$，$N, d_i \leqslant 10^4$ 时约 $10^8$，Python 过不去。更糟的是，它把“每天只能卖一件”摊平成了背包容量，丢掉了过期时间的单调结构。

朴素做法二：按利润降序占最晚空位。 把商品按 $p$ 从大到小排序，每件尽量安排到 $1 \ldots d$ 中最晚的空闲天。这个贪心是对的，但“找最晚空位”若写成 for t in range(d, 0, -1)，最坏仍是 $O(N \cdot \max d)$。

两个朴素做法的共同瓶颈：都在反复扫描同一段时间轴。要跳出这个瓶颈，需要换一个提问方式。

关键转变：不预先决定“卖在哪一天”，只决定“卖不卖”。

有了可行性判据，“具体排在哪天”总可以事后再补，于是按 $d$ 扫描时只需盯住可行性判据里最紧的那个前缀条件：

把候选商品按 $d$ 升序排列，对每个前缀，入选件数不能超过该前缀中最大的那个 $d$。

（把这一步拆开说清楚：处理完所有 $d \leqslant D$ 的商品后，判据中每一个 $j \leqslant D$ 的条目都已确定；而此后新加入的商品过期时间都 $> D$，只能占用 $D+1$ 及以后的天，不会再来挤前 $D$ 天。所以在扫到 $D$ 时逐个检查“已选件数 $\leqslant D$”，就等价于完整地执行了可行性判据。）

换个更具体的说法：扫描到第 $d$ 天时，手头所有过期时间 $\leqslant d$ 的商品只能占用第 $1 \ldots d$ 天，也就是最多留下 $d$ 件。

于是算法成形了——按 $d$ 升序扫描，维护一个“暂定要卖”的集合：

1. 每读到一件商品，先假设它卖得出去，把 $p$ 放进去；
2. 扫到第 $d$ 天时，如果集合大小超过 $d$，就必须丢掉一件；
3. 丢哪一件？丢利润最小的那件。

第 3 步的安全性来自一次交换论证：被丢的那件利润 $\leqslant$ 集合内其余任何一件，而它们的可用时间集合完全一样（都 $\leqslant d$），把名额让给利润更大的同伴，收益只增不减。这也是“反悔贪心”这个名字的来源：先收下，将来遇到更贵的再把便宜的退掉。

“随时插入、随时取最小”正是小根堆的接口：heappush 之后若堆大小超过 $d$，就 heappop 弹出最小值。

对照代码，扫描过程只做三件事：heappush(heap, p) 对应“先收下”，if len(heap) > d 对应“容量不够”，heappop(heap) 对应“退掉利润最小的”。

用第二组样例（$N = 7$）走一遍完整过程，$d_i$ 升序后依次是 $(d,p) = (1,20), (1,2), (2,100), (2,8), (3,10), (10,50), (20,5)$：

表的列依次是步数、当前商品的过期时间与利润、本步动作、堆内容、堆大小和本步的容量上限 $d$。第 2 步和第 4 步是两次典型的反悔：利润 20 挤掉 2、利润 100 挤掉 8，都是“先收下、再退掉最差的”。第 5 步之后堆大小是 3、容量是 3，刚好卡满；第 6、7 步过期时间远大于件数，不再触发弹出。最终堆内 5 件商品之和 $10 + 20 + 50 + 100 + 5 = 185$，与样例输出一致。

最优性证明。 交换论证只能说明“单步看起来不吃亏”，要说明全局最优需要一条不变量。为了避免跟踪“商品序号”，改为按最大截止日期 $D$ 归纳（$D$ 从 $0$ 到 $10000$）。记

• $P_D$：所有 $d_i \leqslant D$ 的商品；
• $A_D$：按 $d$ 升序处理完 $P_D$ 后堆的状态（即处理完所有 $d = D$ 的商品、并已弹过之后）；
• $\mathrm{top}_t(X)$：多重集 $X$ 中最大的 $\min(t, |X|)$ 个元素之和；
• $\mathrm{OPT}_t(P_D)$：从 $P_D$ 中选出的、件数不超过 $t$ 的可行子集的最大利润和。

归纳假设（对 $D-1$ 成立）：(a) $A_{D-1}$ 可行；(b) $\mathrm{OPT}_t(P_{D-1}) = \mathrm{top}_t(A_{D-1})$ 对一切 $t$ 成立。归纳起点 $D = 0$：没有商品，空堆可行且两边都是 $0$。

现在处理 $d = D$ 的那批商品 $N$。算法把它们依次压入，每压一次只要堆大小超过 $D$ 就弹掉最小值；这正是经典的“小根堆维护前 $k$ 大”过程，所以结束时堆里恰好是 $H' = A_{D-1} \cup N$ 中最大的 $\min(|H'|, D)$ 个元素，记作 $A_D$。要证 $\mathrm{OPT}_t(P_D) = \mathrm{top}_t(A_D)$：

• 下界（先证 (a) $A_D$ 可行，于是它是候选解）：对 $j < D$，$A_D$ 中 $d \leqslant j$ 的商品就是 $A_{D-1}$ 中 $d \leqslant j$ 的那些（新商品的 $d = D > j$），由归纳假设 (a) 其数量 $\leqslant j$；对 $j \geqslant D$，数量等于 $|A_D| \leqslant D \leqslant j$。所以 $A_D$ 满足可行性判据。它的前 $t$ 大给出一个件数 $\leqslant t$ 的可行解，故 $\mathrm{OPT}_t(P_D) \geqslant \mathrm{top}_t(A_D)$。

• 上界：任取可行子集 $T \subseteq P_D$ 且 $|T| \leqslant t$。拆成 $T = T' \cup T''$，其中 $T' \subseteq P_{D-1}$、$T'' \subseteq N$。由归纳假设 $\sum T' \leqslant \mathrm{top}_{|T'|}(A_{D-1})$；把 $A_{D-1}$ 中最大的 $|T'|$ 个取出、再并上 $T''$，得到 $H'$ 的一个子多重集 $M$，则

  $$\sum T \;=\; \sum T' + \sum T'' \;\leqslant\; \sum M .$$

  注意 $M$ 恰好含有 $|T'| + |T''| = |T|$ 个元素。由可行性判据（取 $j = |T|$）知 $|T| \leqslant d_{(|T|)} \leqslant D$，所以 $|M| = |T| \leqslant D$。

  • 若 $t \leqslant |A_D|$：$\sum M \leqslant \mathrm{top}_t(H')$，而 $A_D$ 是 $H'$ 中最大的 $|A_D|$ 个，截取前 $t$ 大得到 $\mathrm{top}_t(H') = \mathrm{top}_t(A_D)$，结论成立。
  • 若 $t > |A_D|$：此时 $\mathrm{top}_t(A_D) = \sum A_D$。又分两种：没弹过元素时 $A_D = H'$，则 $\sum M \leqslant \sum H' = \sum A_D$；弹过元素时 $|A_D| = D$，而 $|M| \leqslant D$，故 $\sum M \leqslant \mathrm{top}_D(H') = \sum A_D$。

所以 $\mathrm{OPT}_t(P_D) = \mathrm{top}_t(A_D)$，且 (a) 已在上面证得，归纳完成。

取 $D = \max d_i$（于是 $P_D$ 就是全部商品）与 $t = N$，得 $\mathrm{OPT}_N(P_D) = \mathrm{top}_N(A_D) = \sum A_D$：堆内所有元素之和就是最大收益，且这个不变量刚好就是“堆里的前 $t$ 大是每个件数档位的最优解”这一嵌套性质。

实现要点。 读入有两处要小心：题面允许数据间任意穿插空格与空行，所以必须整体 split() 而不能按行解析；真实数据文件以 DOS 结束符 0x1A 结尾，需要把它替换成空白，否则 int() 会抛 ValueError。多组数据用 for n in data: 一路读到 EOF，不需要预先知道组数；$N = 0$ 时循环体不执行，sum([]) 直接给出 0。

代码

代码分两层：best_profit 负责单组的“按 $d$ 扫描 + 堆反悔”，solve 只管读入、按组切分和输出。deals 里存的是 $(d, p)$ 而不是题面的 $(p, d)$，这样 sorted(deals) 天然按过期时间升序，不必写 key=；函数内的 d、p 与题面的 $d_i$、$p_i$ 一一对应。

Python 版：

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#!/usr/bin/env python3
# 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-01 11:52
# update_at: 2026-10-01 11:52

import sys
from collections.abc import Iterator
from heapq import heappop, heappush

DOS_EOF = b'\x1a'  # 老数据文件的 DOS 结束符，当作空白丢弃


def best_profit(deals: list[tuple[int, int]]) -> int:
    """deals 里每项是 (过期时间 d, 利润 p)，返回这一组商品的最大收益。

    按 d 升序扫描，堆里只装"暂定要卖"的利润，堆的大小就是这些商品占用的天数：
    截至第 d 天最多卖出 d 件，所以处理完过期时间为 d 的一批后，堆若超过 d 个，
    就弹出最小的那个利润——它被放弃，换来的名额留给更值钱的商品。
    """
    heap: list[int] = []
    for d, p in sorted(deals):          # 元组比较先看 d，天然按过期时间升序
        heappush(heap, p)
        if len(heap) > d:               # 第 1..d 天一共只有 d 个摊位
            heappop(heap)               # 忍痛丢掉利润最小的那件
    return sum(heap)


def solve() -> None:
    raw = sys.stdin.buffer.read().replace(DOS_EOF, b' ')
    data: Iterator[int] = iter(map(int, raw.split()))
    out: list[str] = []

    for n in data:                      # 每组用例以 N 开头，读到文件结尾为止
        deals: list[tuple[int, int]] = []
        for _ in range(n):
            p, d = next(data), next(data)   # 题面顺序：先利润 p_i，后过期时间 d_i
            deals.append((d, p))
        out.append(str(best_profit(deals)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 15:50
 * update_at: 2026-10-06 15:50
 */

// 3043 超市：反悔贪心（按过期时间升序扫描 + 小根堆）
// 可行性判据：把子集按 d 升序排好后，第 j 小的 d 必须 >= j，
// 所以按 d 扫描时只需保证：处理完所有 d <= D 的商品后，暂定集合大小 <= D。
// 扫描到商品 (p, d) 时，手头所有过期时间 <= d 的商品只能占第 1..d 天，
// 一旦堆大小超过 d，就丢掉利润最小的那件（可用时间相同，留大的不吃亏）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 小根堆：暂定要卖的商品利润；堆内元素之和就是当前最优收益
priority_queue<ll, vector<ll>, greater<ll> > heap;

int main() {
    // 题面允许数据间任意穿插空格与空行，直接按空白流式读入直到 EOF
    ll n;
    while (cin >> n) {
        // 用 pair 的天然排序：first = d（过期时间），second = p（利润）
        vector<pair<ll, ll> > deals; // deals[i] = (d_i, p_i)
        deals.resize(n);
        for (ll i = 0; i < n; ++i) {
            ll p, d;
            cin >> p >> d;
            deals[i] = make_pair(d, p);
        }
        sort(deals.begin(), deals.end()); // 按过期时间 d 升序

        while (!heap.empty()) heap.pop(); // 清空上一组的堆
        for (ll i = 0; i < n; ++i) {
            ll d = deals[i].first;
            ll p = deals[i].second;
            heap.push(p); // 先假设这件商品卖得出去
            ll sz = heap.size();
            if (sz > d) heap.pop(); // 第 1..d 天只有 d 个摊位，退掉最小利润
        }

        ll ans = 0;
        while (!heap.empty()) {
            ans += heap.top();
            heap.pop();
        }
        cout << ans << "\n";
    }
    return 0;
}

复杂度

• 时间复杂度：单组排序 $O(N \log N)$，每件商品至多一次 heappush 和一次 heappop，各 $O(\log N)$，合计 $O(N \log N)$。相比两个 $O(N \cdot \max d)$ 的朴素做法（$N = 10^4$ 时约 $10^8$ 次操作），本做法只需 $10^5$ 量级的基本操作，与 C++ 的二叉堆 / 并查集标准做法同阶。
• 空间复杂度：$O(N)$，deals 存 $N$ 个二元组、heap 最多 $N$ 个整数。真实数据 d1.in 的 15 组数据合计运行 0.052 s、峰值 26.2 MB，相对 1000 ms / 128 MB 的限制十分宽裕。

总结

本题的核心是把"哪一天卖"这个显式排期问题，等价替换成"卖不卖"这个前缀容量问题：把商品按过期时间升序扫描，候选集合的大小一旦超过当前天数 $d$，就说明第 $1 \ldots d$ 天装不下这么多件，必须放弃一件；放弃利润最小的那件不会损失最优性，因为同批候选的可用时间集合完全相同。小根堆正好支持"随时插入 + 取出最小"，把这个反悔过程写成三行循环，总复杂度 $O(N \log N)$。实现上还要注意两处输入细节：按空白切分读入以兼容任意空格空行，以及把数据文件末尾的 DOS 结束符 0x1A 当空白处理。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7每组商品: (利润 p_i, 过期时间 d_i)
`- 换成 (d_i, p_i) 并按 d 升序扫描     <= 容量 d 只增不减
   `- 先假设每件都卖, 压入小根堆
      |- 堆大小 <= d   -> 全部卖得出去, 继续
      `- 堆大小 >  d   -> 第 1..d 天只有 d 个摊位, 必须丢掉一件
         `- 丢掉堆中最小的利润            <= 反悔: 名额留给后面更贵的
            `- 扫完后堆内元素之和 = 最大收益

先看第一层为什么要换成 $(d_i, p_i)$ 排序：只有按过期时间扫描，容量 $d$ 才单调不减，堆的"超容量就弹"才是一个单调推进、不会反复的判据。再看分叉的两支：堆没超容量说明当前这些商品总能找到日子卖；超容量说明第 $1 \ldots d$ 天一共只有 $d$ 个摊位，必须放弃一件，而放弃最小的那件是安全的——它的利润不大于任何同伴，可用时间集合又完全一样。图中最右侧那句"堆内元素之和 = 最大收益"，正是上面嵌套式贪心不变量在 $k = N$、$t = N$ 时的结论。