优先队列的应用（Work Scheduling）

Work Scheduling

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 34 Accepted Submission(s): 3

Description

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 ≤ N ≤ 100,000) jobs conveniently numbered 1..N for work to do. It is possible but extremely unlikely that he has time for all Njobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 ≤ D_i ≤ 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 ≤ P_i ≤ 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

Input

Multipel test cases. For each case :

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

Output

For each case, output one line : A single number on a line by itself that is the maximum possible profit FJ can earn.

Sample Input

3
2 10
1 5
1 7

Sample Output

Hint

Complete job 3 (1, 7) at time 1 and complete job 1 (2, 10) at time 2 to maximize the earnings (7 + 10 → 17).

Source

USACO 2009 Open

1-100000000个单位时间内可以做n项工作，每项工作需要1个单位时间，截止时间为Di，价值为Pi。

运用贪心，将时间从小到大排序，取价值最大的工作。

用优先队列

 1 #include<bits/stdc++.h>
 2 #define man 100006
 3 #define ll long long
 4 using namespace std;
 5 ll n,ans;
 6 priority_queue<ll,vector<ll>,greater<ll> >in；///优先队列
 7 typedef struct W{
 8     ll ti,cost;
 9 };
10 W work[man];
11 
12 bool cmp(W a, W b)
13 {
14     return a.ti<b.ti;
15 }
16 
17 int main()
18 {
19     while( ~scanf("%lld",&n)){
20         ll x,y,si=0;
21         while(!in.empty())
22             in.pop();
23         for(int i=1;i<=n;i++){
24             scanf("%lld%lld",&x,&y);
25             work[i].ti=x;
26             work[i].cost=y;
27         }
28         sort( work+1, work+1+n, cmp);
29         ans=0;
30         for(int i=1;i<=n;i++){
31             if(si<work[i].ti){
32                 si++;
33                 in.push(work[i].cost);
34                 ans+=work[i].cost;
35             }
36             else{
37                 if(work[i].cost<=in.top())
38                     continue;
39                 ans-=in.top();
40                 ans+=work[i].cost;
41                 in.pop();
42                 in.push(work[i].cost);
43             }
44         }
45 
46         printf("%lld
",ans);
47     }
48     return 0;
49 }

View Code