题目地址：
https://www.acwing.com/problem/content/147/
超市里有
N
N
N
件商品，每件商品都有利润
p
i
p_i
p
i
和过期时间
d
i
d_i
d
i
，每天只能卖一件商品，过期商品不能再卖。求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
输入格式：
输入包含多组测试用例。每组测试用例，以输入整数
N
N
N
开始，接下来输入
N
N
N
对
p
i
p_i
p
i
和
d
i
d_i
d
i
，分别代表第
i
i
i
件商品的利润和过期时间。在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。
输出格式：
对于每组产品，输出一个该组的最大收益值。每个结果占一行。
数据范围：
0
≤
N
≤
10000
0≤N≤10000
0
≤
N
≤
1
0
0
0
0
1
≤
p
i
,
d
i
≤
10000
1≤p_i,d_i≤10000
1
≤
p
i
,
d
i
≤
1
0
0
0
0
最多有
14
14
1
4
组测试样例
法1：优先队列。先将所有商品按照过期日从小到大排序，然后开个小顶堆存计划卖出的商品，价格低者优先。接下来遍历商品，如果当前的商品的过期日大于堆的元素个数，说明当前商品可以和堆内商品一同卖出，直接入堆；如果当前商品过期日等于堆的元素个数，意味着当前商品无法与堆里的所有商品一起卖出，必须有取舍，那么比较一下当前商品和堆顶商品的价格，如果当前商品价格高，显然卖当前商品划算，就把堆顶pop出来，将当前商品push进堆。最后堆内商品即为能取得最大收益的商品组合。其实遍历商品的过程是在枚举到期日
t
t
t
，而堆里维护的是在不卖过期商品的前提下价值前
t
t
t
大的商品。容易看出最优解的形式一定是某几个到期日到期的商品挑价值最高的若干个，这个非常容易证明。接下来再用数学归纳法证明算法的正确性，如果最优解里没有第
n
n
n
个商品，算法显然正确；如果有，由归纳假设，算法能得出前
n
−
1
n-1
n
−
1
个商品的最优解，如果第
n
n
n
个商品可以直接加进去，那算法也显然正确；如果第
n
n
n
个商品不能直接加进去，设其到期日为
d
d
d
，由归纳假设，堆里已经存了
d
d
d
个商品，且它们就是前
n
−
1
n-1
n
−
1
个商品里要求不卖过期商品的情况下前
d
d
d
大价值的商品。显然如果前
n
−
1
n-1
n
−
1
个商品里如果只能选
d
−
1
d-1
d
−
1
个商品的话，最优解一定是将最便宜的那个踢掉（这一点看下面的并查集解法会更加清楚），加上第
n
n
n
个商品就是最优解。
代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e4 + 10;
using PII = pair<int, int>;
int n;
priority_queue<PII, vector<PII>, greater<PII>> heap;
vector<pair<int, int>> a;
int main() {
while (cin >> n) {
heap = priority_queue<PII, vector<PII>, greater<PII>>();
a.clear();
for (int i = 0; i < n; i++) {
int v, d;
scanf("%d%d", &v, &d);
a.push_back({d, v});
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
int d = a[i].first, v = a[i].second;
if (d > heap.size()) heap.push({v, d});
else if (v > heap.top().first) {
heap.pop();
heap.push({v, d});
}
}
int res = 0;
while (heap.size()) {
res += heap.top().first;
heap.pop();
}
printf("%d\n", res);
}
return 0;
}
时间复杂度
O
(
n
log
n
)
O(n\log n)
O
(
n
lo
g
n
)
，空间
O
(
n
)
O(n)
O
(
n
)
。
法2：并查集。将商品按照价值从大到小排序，我们考虑优先卖出价值大的商品，并且每个商品尽量在临近其到期日的时候卖出。开一个并查集，每个位置表示到期日，每个到期日的父亲节点定义为其之前最近的还没分配商品去卖的日子。遍历商品，看其到期日之前有没有空位，如果有，则选进组合，并标记一下该到期日之前的空位为空位的前一位；如果没空位，则不能选进组合，继续考虑下一个商品。考虑如何证明。用数学归纳法 + 反证法。假设算法得出的不是最优解，考虑一个”更优解“，依然将所有商品按照价格从高到低排序，然后按顺序遍历所有商品，找到更优解中没选但是最优解里选了的第一件商品，设其为商品
i
i
i
（注意，如果更优解与最优解不同，那么一定是最优解里选了某个商品但是更优解里没选，而不可能相反，因为算法是尽量将商品安排在尽可能到期的时间卖出的，如果更优解选了但是最优解没选，这个更优解一定是不合法的），接下来由归纳假设，在更优解里商品
i
i
i
之后的商品用算法得出最优解，那我们可以将更优解在最优解里商品
i
i
i
卖出的日期的那天卖出的商品用商品
i
i
i
替换掉（如果没有，就加卖之），这样得出了不比更优解更差的解，说明商品
i
i
i
是可以被选中在那天卖的。说明最优解不差于更优解，说明算法得出的就是最优解。
代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4 + 10;
int n;
int p[N];
vector<pair<int, int>> a;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
while (cin >> n) {
int res = 0, maxd = 0;
a.clear();
for (int i = 0; i < n; i++) {
int v, d;
scanf("%d%d", &v, &d);
a.push_back({v, d});
maxd = max(maxd, d);
}
for (int i = 0; i <= maxd; i++) p[i] = i;
sort(a.begin(), a.end(), greater<pair<int, int>>());
for (int i = 0; i < a.size(); i++) {
int v = a[i].first, d = a[i].second;
int date = find(d);
if (date) {
res += v;
p[date] = date - 1;
}
}
printf("%d\n", res);
}
return 0;
}
时间复杂度
O
(
n
(
log
n
+
log
∗
M
)
)
O(n(\log n+\log^*M))
O
(
n
(
lo
g
n
+
lo
g
∗
M
)
)
，这里的
M
M
M
指的是最大到期日，空间
O
(
n
+
M
)
O(n+M)
O
(
n
+
M
)
。