题号 NC50995
名称 Supermarket
来源 0x17基本数据结构-二叉堆
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



感谢@jxnu-19-软技一班-刘晟推荐题目，100牛币奖励已发放~
原博客链接：https://blog.nowcoder.net/n/2ce3a846aeb54e2b96957fdca7972cdd
如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

题号：NC50995，蓝书上面的题目，难度不大，简单思维+基本算法（堆或者并查集）

推荐理由and知识点：简单贪心攻略比较锻炼到我，再结合可以多方面思考解题方法，从堆和并查集两方面（基本的算法结构）都可以解题。

中文题目大意：
多组输入、给定N个商品，每个商品有利润pi和过期时间di，每天只能卖出一个商品，过期商品不能再卖，如何安排每天卖的商品，可以使得利益最大。。

极其不推荐做法：直接暴力贪心从利润大到小排序，从最大利润商品开始；用一个j初始化为该商品过期时间，直到大于等于0，找到一天空闲卖出，累加利润，break；时间复杂度O(n^2) ，题目比较水，建议卡掉这种办法，可以通过下面并查集优化得到正确解法。
解题思路1（二叉堆优化）：
容易想到一个贪心策略：在最优解里面，每一天t中，应该在保证卖出商品都是没有过期得前提下，尽可能卖出利润前t大得商品。因此，我们可以依次考虑每个商品，动态的维护一个满足上面性质得方案。
具体到代码中就是，按照商品过期天数递增排序，建立一个小根堆，因为STL中存在优先队列直接使用就行了。我们使得小根堆中得元素保存为我们每一天需要卖出的商品利润，最终求和。
从1开始遍历N件商品，因为商品以及按过期时间排序，所以分为下面2种情况。
1、如果该商品的过期时间，大于现在堆中元素个数，说明一定可以找个时间把它卖出去，直接插入堆中。
2、否则，就是当前这件商品过期时间t内，安排了t件商品出售，我们需要拿到堆顶元素(收益最小)，与这件商品收益对比，如果这件商品收益大，那我们就选择更换商品在这一天出售。（或者说当存在多件商品过期天数相同的情况下，我们看是不是要在前t天中少买一件别的商品，把它卖出去）

该算法时间复杂度O(N * log N)
Code1

#include
using namespace std;
struct Node {
    int p, d;
}a[10005];
bool cmp1(Node a, Node b) {
    return a.d < b.d;
}
priority_queue, greater > pq; //存储我们卖的物品价值
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d %d", &a[i].p, &a[i].d);
        }
        // 按照过期时间升序排序
        stable_sort(a + 1, a + 1 + n, cmp1);
        for (int i = 1; i <= n; ++i) {
            int t = a[i].d;
            if (t > pq.size())   pq.push(a[i].p); // 情况1
            else { //情况2(过期时间与前一个商品相同时)
                int pp = pq.top();
                if (pp < a[i].p) { //比较是否更换，如果收益更大选择替换
                    pq.pop();
                    pq.push(a[i].p);
                }
            }
        }
        int ans = 0;
        while (pq.size()) { //遍历优先队列全部元素，累加求和就是答案
            ans += pq.top();
            pq.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}

解题思路2（并查集优化）：
上面我们通过二叉堆，有了一种解题方法，还有另一种优化方法，就是使用并查集，想想为什么我们最开始暴力贪心不行因为第二重枚举用时太大，可以通过一个并查集数组来减少我们的时间开销，达到优化目的。
1、首先我们按照商品的收益降序排序，收益越大越早处理，并且根据贪心思想，我们要保证“决策包容性”所以我们在选择找个商品出售时间都应该选择尽可能晚的卖出去。
2、这样建立一个关于“天数”的并查集f，初始化为-1，我们用x表示该商品过期时间天数，Find（x），如果f[x]==-1；说明这一天没有商品被卖出去，直接让该商品在这一天卖出去，用一个变量t接受卖出去的天数；并且合并f[t]=t-1，并且累加利润；即下一次访问这个天数，根据并查集特性访问前一天是否合法。直到Find（）结束。如果Find返回的不是0；就说明找到了一天空闲，可以安排一天把该商品出售，累加利润，f[t]=t-1;否则如果t==0，说明在该商品过期天数内，存在也会过期，并且利润比你大的商品，只能放弃该商品不卖，继续遍历下一个商品。直到全部商品遍历完毕，最终利润和求解完毕

该算法用时应该比二叉堆快一点
Code2:

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e4;
struct Node {
    int p, d;
    bool operator <(const Node& a)const {
        return this->p > a.p;
    }
}p[N + 5];
int f[N + 5];

int find(int x) {
    if (f[x] == -1) return x;
    return f[x] = find(f[x]);
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        memset(f, -1, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            p[i].p = read();
            p[i].d = read();
        }
        stable_sort(p + 1, p + 1 + n); //价值降序排序
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int t = find(p[i].d); //返回可以出售的最小时间
            if (t > 0) { //如果找到有一天可以出售该商品
                ans += p[i].p; //累加利润
                f[t] = t - 1; //合并t和t-1
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目6月22日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴