51nod 1163贪心

时间:2023-11-09 20:15:38

用优先队列来贪心,是一个很好地想法。优先队列在很多时候可以维护最值,同时可以考虑到一些其他情况。

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1163

#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 99999999
#define ll __int64
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
struct node
{
int x;
int val;
}a[MAXN];
int n;
priority_queue<int, vector<int>, greater<int> >q;
bool cmp(node fa, node fb)
{
if(fa.x != fb.x)
return fa.x < fb.x;
return fa.val > fb.val;
}
int main()
{
while(cin >>n){
for(int i = ; i <= n; i++){
cin >>a[i].x >> a[i].val;
}
sort(a+, a+n+, cmp);
while(!q.empty())q.pop();
int t = ;
for(int i = ; i <= n; i++){
if(t < a[i].x){
t ++;
q.push(a[i].val);
}
else if(t == a[i].x){
int temp = q.top();
q.pop();
if(temp < a[i].val){
temp = a[i].val;
}
q.push(temp);
}
}
ll ans = ;
while(!q.empty()) {
int temp = q.top();
q.pop();
ans += temp;
}
cout<<ans<<endl;
}
}