优先队列+贪心
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int t;
int w;
}a[50010];
bool comp(node x,node y){
if(x.t!=y.t){
return x.t<y.t;
}
return x.w>y.w;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].w;
}
sort(a+1,a+1+n,comp);
priority_queue<int,vector<int>,greater<int> >q;
for(int i=1;i<=n;i++){
if(q.size()<a[i].t){
q.push(a[i].w);
}
else{
if(q.top()<a[i].w){
q.pop();
q.push(a[i].w);
}
}
}
ll ans=0;
while(q.size()){
ans+=(ll)q.top();
q.pop();
}
cout<<ans<<endl;
return 0;
}
并查集优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int t,w;
}a[50010];
bool comp(node x,node y){
if(x.w==y.w) return x.t<y.t;
else return x.w>y.w;
}
int fa[50010];
int find(int x){
if(x<0) return -1;
if(x==fa[x]) return fa[x]=x-1;
else return fa[x]=find(fa[x]);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].w;
fa[i]=i;
}
sort(a+1,a+1+n,comp);
ll ans=0;
for(int i=1;i<=n;i++){
if(find(a[i].t)>=0) ans+=(ll)a[i].w;
}
cout<<ans<<endl;
return 0;
}