超市
题意
超市里有 N 件商品，每件商品都有利润 p i和过期时间 d i 每天只能卖一件商品，过期商品不能再卖。
求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
思路
首先将所有商品按照过期时间非严格单调递增排序，然后遍历每一件商品。将 S 定义为已经选择要卖的商品的集合，如果将当前遍历到的商品 node[i] 加入集合后，集合的大小小于等于 node[i]的过期时间 d i那么符合继续遍历接下来的商品。否则，将当前集合中价值最小的商品移除，直到与 d i i相等为止
代码
#include<bits/stdc++.h> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e5 + 10; int n; struct Node { int p, d; }; void solve() { while (scanf("%d", &n) != EOF) { int res = 0; priority_queue<Node>pq; for (int i = 1; i <= n; ++i) { int p, d; cin >> p >> d; if (pq.size() < d)pq.push({ p, d }); else { if (pq.size() && pq.top().p < p) { pq.pop(); pq.push({ p, d }); } } } while (pq.size()) { res += pq.top().p; pq.pop(); } cout << res << endl; } } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
