竞赛讨论区 > 【每日一题】6月15日题目精讲
头像
王清楚
编辑于 2020-06-15 11:46
+ 关注

【每日一题】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之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

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

全部评论

(17) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐