Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贪心+pq 79ms1A

Posted by KatrineYang at 2016-11-08 11:55:42 on Problem 1456
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator