Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贪心+pq 79ms1A#include <iostream> #include <stdio.h> #include <algorithm> #include <queue> using namespace std; struct prod{ int price,ddl; }P[10005]; bool cmp(const prod &p1, const prod &p2){ return p1.ddl > p2.ddl; } bool operator<(const prod &p1, const prod &p2){ return p1.price < p2.price; } int main() { int n; while(scanf("%d",&n)>0){ int mxt = 0; for(int i = 0; i < n; i++){ scanf("%d%d",&P[i].price, &P[i].ddl); if(mxt < P[i].ddl) mxt = P[i].ddl; } sort(P, P+n, cmp); priority_queue<prod> pq; int res = 0, pos = 0; for(int i = mxt; i > 0; i--){ while(pos < n && P[pos].ddl == i){ pq.push(P[pos]); pos++; } if(!pq.empty()){ res += pq.top().price; pq.pop(); } } printf("%d\n",res); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator