【每日一题】Supermarket 优先队列

description

有n件商品 每件有利润和过期时间 卖出这些商品能获得的最大利润是多少

solution

这题算是很经典的题，首先贪心的想法肯定要按时间大小排序，能卖越多越好，其次就是如果我当前利润获得一样而另一个物品时间更长，这明显就是更优的选择，所以采用优先队列，有重新选择的机会，使得答案最优，这样就可以通过该题，时间复杂度O(n*log(n))

code

#include <bits/stdc++.h>

using namespace std;

struct node {
  int v, d;
  friend bool operator < (const node &a, const node &b) { 
      return a.d < b.d; 
  }
};
node a[10005];

int main() {
  ios::sync_with_stdio(0);
  int n;

  while (cin >> n) {
    priority_queue <int, vector<int>,greater<int> > q;

    for (int i = 0; i < n; i++) {
      cin >> a[i].v >> a[i].d;
    }

    sort(a, a + n);

    for(int i = 0;i < n;i ++){
        int t = a[i].d;
        if(t > q.size()){
            q.push(a[i].v);
        }else{
            int v = a[i].v;
            if(v > q.top()){
                q.pop();
                q.push(v);
            }
        }
    }
    int res = 0;
    while(!q.empty()){
        res += q.top();
        q.pop();
    }
    cout << res << '\n';
  }
  return 0;
}