思路:按时间贪心,每次更新前面几天能卖出的最大利润,用堆可以自动排序,每次筛出堆顶元素最小的那个,所以用小根堆就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
pair<int,int> a[N];
int main()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i].second>>a[i].first;
}
sort(a,a+n);
priority_queue<int,vector<int>,greater<int>> h;
for(int i=0;i<n;i++){
h.push(a[i].second);
if(h.size()>a[i].first) h.pop();
}
long long ans=0;
while(h.size()){
ans+=h.top();
h.pop();
}
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号