首页 > Windows开发 > 详细

AcWing - 145 - 超市 = 贪心

时间:2019-09-12 23:32:54      阅读:101      评论:0      收藏:0      [点我收藏+]

https://www.acwing.com/problem/content/147/

有n个商品,商品有价格和过期时间,在过期时间之前才可以卖出,每天只能卖一个。求最大利润。

假如直接对过期时间排序然后贪心会WA。事实上先把所有物品按过期时间排序,把商品的价格放进小顶堆里面,检测到一个商品的过期时间<当前堆的大小时,说明现在的时间不够出售所有的商品,就把价格最小的丢掉。为什么这样的对的呢?每次调整完之后堆里的东西要么是卖得完还充裕的,那么剩下的商品之间填充多出来的时间。否则是(当前时间点)刚刚好够的,每个物品都能找到在他过期之前的一个时间卖出。

假如新加进去的商品价格最低,直接把它丢了。否则我换出一个商品,这个商品不是新加进去的,那么被换出的位置肯定足够容纳新来的那个商品。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

pair<int, int> p[10005];
priority_queue<int, vector<int>, greater<int> > pq;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            p[i] = {y, x};
        }
        sort(p + 1, p + 1 + n);
        for(int i = 1; i <= n; ++i) {
            pq.push(p[i].second);
            while(p[i].first < pq.size())
                pq.pop();
        }
        ll sum = 0;
        while(!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
        printf("%lld\n", sum);
    }
}

AcWing - 145 - 超市 = 贪心

原文:https://www.cnblogs.com/Inko/p/11515413.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!