C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 4200K, 提交时间: 2020-05-14 15:23:53

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	ll v,s;
}a[100005];
bool cmp(node a,node b)
{
	return a.s>b.s;
}
priority_queue<ll,vector<ll>,greater<ll> >q; 
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;++i)
	cin>>a[i].v>>a[i].s; 
	sort(a+1,a+n+1,cmp);
	ll maxn=0,t=0;
	for(int i=1;i<=n;++i)
	{
		t+=a[i].v;
		q.push(a[i].v);
		while(q.size()>a[i].s)
		{
			t-=q.top();
			q.pop();
		}
		maxn=max(maxn,t);
	}
	cout<<maxn;
 } 

C++ 解法, 执行用时: 91ms, 内存消耗: 5496K, 提交时间: 2022-07-08 16:07:07

#include<bits/stdc++.h>

using namespace std;

#define LL long long

priority_queue<LL,vector<LL>,greater<LL>> q;
vector<LL> ve[100005];

int main()
{
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		LL v,s;
		cin >> v >> s;
		ve[s].push_back(v);
	}
	LL ans=0,sum=0;
	for(int i=n;i>=1;i--)
	{
		for(auto u: ve[i])
		{
			sum+=u;
			q.push(u);
		}
		while(q.size()>i)
		{
			sum -= q.top();
			q.pop();
		}
		ans=max(ans,sum);
	}
	cout << ans;
}

Python3 解法, 执行用时: 384ms, 内存消耗: 21148K, 提交时间: 2021-05-22 00:06:05

from heapq import heappush, heappop
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: -x[1])
ans = cur = 0
q = []
for v, s in a:
	heappush(q, v)
	cur += v
	while len(q) > s: cur -= heappop(q)
	ans = max(ans, cur)
print(ans)