每日一题 Supermarket (优先队列)

一.题意

有N件商品，有利润pi和过期时间di，每天只能卖一件商品，过期商品不能再卖，求最大收益是多少。

二.题解

对于这题，很明显是贪心，肯定是取价格高的物品，但是还要考虑过期时间。
本来是可以考虑枚举过期时间，然后在同一过期时间选择价格最高的物品，但其实这样是不对的。
例如:
4
50 1
60 1
100 2
200 2
可以发现选择过期时间为 2 的两件物品可以取到最高价格，所以考虑同一时间价格最高是不对的。
这个时候我们只需要在前面的策略上加上反悔机制即可。
类似于如果发现前面有物品的价值比他还小，说明可以用该物品替换，这个可以用优先队列优化。
所以可以按照过期时间从小到大排序，这样的话后面如果有价值更大的物品，那么替换优先队列的队头即可。

三.代码:

#include<bits/stdc++.h>
#define pb push_back
#define ld long double
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define endl "\n"
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e7+5;
const int N=1e6+5;
const int mod=1e9+7;
const int mo=1e8;

ll n,m,x,ans,cnt;

struct node{
    ll w,d;
}a[manx];
bool cmp(node a, node b){
    return a.d<b.d;
}

int main(){
    io;  
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].d;
        sort(a+1,a+1+n,cmp);
        priority_queue<ll,vector<ll>,greater<ll> >q;
        for(int i=1;i<=n;i++){
            q.push(a[i].w);
            if(a[i].d<q.size()) q.pop();
        }
        while(q.size()) ans+=q.top(),q.pop();
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}