AcWing 145. 超市
宋标 Lv5
  2022-08-18 02:31:29 2022-08-18 02:31    

题目

超市里有 件商品，每件商品都有利润 和过期时间 ，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式

输入包含多组测试用例。

每组测试用例，以输入整数 开始，接下来输入 对 和 ，分别代表第 件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式

对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围

,

最多有 组测试样例

输入样例：

4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10

输出样例：

80
185

题解

后过期的商品可以提前卖，取利润最大值

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int main()
{
    int T;
    while (cin >> T)
    {
        // 所有商品集合
        vector<PII> vec;
        // 小根堆来存储最终出售的所有商品价格
        priority_queue<int, vector<int>, greater<int>> down;
        while (T --)
        {
            int d, p;
            scanf("%d%d", &p, &d);
            vec.push_back({d, p});
        }

        // 对过期时间升序处理
        sort(vec.begin(), vec.end());

        for (int i = 0; i < vec.size(); ++ i)
        {
            int d = vec[i].first, p = vec[i].second;
            // 由于一天只能卖一件商品，堆中的商品数量大于当前商品的过期时间
            // 所以堆中的商品需要舍弃最小利润的商品
            down.push(p);
            if (down.size() > d) down.pop();
        }

        int sum = 0;
        while (!down.empty()) sum += down.top(), down.pop();

        printf("%d\n", sum);
    }

    return 0;
}
 评论