Description

翻译: 给定价格 和最晚可以卖掉的时间 ，求卖出的最大金额。

Solution1

几年前的老题目了，看了下数据范围，根本不用考虑优化。
对商品按价格从大到小排序，每次选取当前最高价格的，然后从 开始往前找是否有哪一天还没用过，
直接 暴力即可.
PS: 并查集可以优化一下这个过程，懒得写了。

Code1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long inf = 1e18;
const int N = 5e5 + 5, mod = 998244353;

int n;
struct node {
  int l, r;
  bool operator < (const node &s) {
    return l > s.l;
  }
}a[N];
bool vis[N];
int main() {
  while(cin >> n) {
    for(int i = 1; i <= n; i++) {
      cin >> a[i].l >> a[i].r;
      vis[i] = 0;
    }
    sort(a + 1, a + 1 + n);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
      //cout << a[i].l << ' ' << ans << "\n";
      for(int j = a[i].r; j >= 1; j--) {
        if(!vis[j]) {
          vis[j] = 1;
          ans += a[i].l;
          break;
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

Solution2

显然可以优先队列优化，按时间从小到大排序，每次放入一个当前价格最小的，如果能放，直接放进去，否则弹出最小值，放入当前值。
最后答案为优先队列的所有值。
时间复杂度
但是一个 60ms 一个 100ms， 其实差别不大？

Code2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long inf = 1e18;
const int N = 5e5 + 5, mod = 998244353;

int n;
struct node {
  int l, r;
  bool operator < (const node &s) {
    return r < s.r;
  }
}a[N];
bool vis[N];
int main() {
  while(cin >> n) {
    for(int i = 1; i <= n; i++) {
      cin >> a[i].l >> a[i].r;
      vis[i] = 0;
    }
    sort(a + 1, a + 1 + n);
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i = 1; i <= n; i++) {
      q.push(a[i].l);
      if(q.size() > a[i].r) {
        q.pop();
      }
    }
    ll ans = 0;
    while(!q.empty()) {
      ans += q.top();
      q.pop();
    }
    cout << ans << "\n";
  }
  return 0;
}