注意点:不能先按时间排序,在每个时间点选最大的。如果第一秒有p1=1,第二秒有p2=10和p3=11,则如果按时间来,则先选第一秒的1,再选第二秒的 11;但是有更优的策略:第一秒选p3,第二秒选p2。
开long long
#include <bits/stdc++.h> using namespace std; const long long int N = 1e5 + 10; long long int n, ans; struct NODE { long long int d, p; bool operator>(const NODE &b) const { return p > b.p; } // 元宝数大的在前面 } a[N]; priority_queue<NODE, vector<NODE>, greater<NODE>> q; // 最小p堆 bool cmp(NODE a, NODE b) { // 按时间从小到大排序 return a.d < b.d; } int main() { cin >> n; for (long long int i = 1; i <= n; i++) { cin >> a[i].d >> a[i].p; } sort(a + 1, a + n + 1, cmp); for (long long int i = 1; i <= n; i++) { // q存每一秒要取的NODE if (a[i].d > q.size()) { q.push(a[i]); } else if (q.top().p < a[i].p) { // 当前i元宝数更多:反悔操作取a[i] q.pop(); q.push(a[i]); } } while (!q.empty()) { ans += q.top().p; q.pop(); } cout << ans; return 0; }