跟MT3029战神小码哥类似，都是贪心+堆。注意开long long
这里的堆顶为战斗力最小的，便于贪心的反悔操作。先按容忍度从大到小排序（q中总容忍度取决于最小的容忍度），再向q中存数，存到不能容忍之后再把堆顶踢出，取最大值。
#include <bits/stdc++.h> using namespace std; const long long int N = 1e5 + 10; long long int n, ans, sum; struct node { long long int a; long long int b; bool operator>(const node &b) const { return a > b.a; } } a[N]; priority_queue<node, vector<node>, greater<node>> q; // 战斗力从小到大排列 bool cmp(node a, node b) { // 按b容忍度从大到小排序 return a.b > b.b; } int main() { cin >> n; for (long long int i = 1; i <= n; i++) { cin >> a[i].a >> a[i].b; } sort(a + 1, a + n + 1, cmp); // 按容忍度从大到小排列 for (long long int i = 1; i <= n; i++) { q.push(a[i]); sum += a[i].a; // 存战斗力 while (q.size() > a[i].b) { sum -= q.top().a; // 取出q.top()战斗力最小的 q.pop(); } ans = max(ans, sum); } cout << ans; return 0; }
