7 4 20 2 60 4 70 3 40 1 30 4 50 6 10Sample Output
230
#include <iostream> #include <cstdio> #include <queue> #include <map> #include <algorithm> using namespace std; int n; struct assign { int time,award; friend bool operator <(assign a,assign b) { return a.award>b.award; } }as[50000]; int cmp(assign a,assign b) { return a.time<b.time; } int main() { int n; long long sum=0; priority_queue <assign>q; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d %d",&as[i].time,&as[i].award); } sort(as,as+n,cmp); for(int i=0;i<n;i++) { q.push(as[i]); sum+=as[i].award; if(i<n-1&&as[i+1].time!=as[i].time) { while(q.size()>as[i].time) { sum-=q.top().award; q.pop(); } } } while(q.size()>as[n-1].time) { sum-=q.top().award; q.pop(); } printf("%lld",sum); }
原文:http://www.cnblogs.com/8023spz/p/7225167.html