【每日一题】6月15日题目精讲
题号 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之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
美团公司氛围 1906人发布
