【优先队列+贪心】POJ2431-Expedition

解题方法详见《挑战程序设计竞赛（第二版）》P74-75。注意首先要对加油站以位置为关键字快排，不要遗忘把终点视作一个加油量为0的加油站，否则最终只能到达终点前的加油站。

 1 /*优先队列*/ 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=10000+5;
 8 
 9 struct rec
10 {
11     int pos,oil;
12     bool operator < (const rec& x) const
13     {
14         return pos<x.pos;
15     }
16 };
17 
18 rec sta[MAXN];
19 int n,L,P,a,t=0;
20 
21 void input()
22 {
23     scanf("%d",&n);
24     for (int i=0;i<n;i++) scanf("%d%d",&sta[i].pos,&sta[i].oil);
25     scanf("%d%d",&L,&P);
26     for (int i=0;i<n;i++) sta[i].pos=L-sta[i].pos;
27     sta[n].pos=L;//把终点也作为加油站 
28     sta[n].oil=0;
29     n++;
30 }
31 
32 void doit()
33 {
34     priority_queue<int> pque;
35     sort(sta,sta+n);
36     int npos=0;
37     for (int i=0;i<n;i++)
38     {
39         int d=sta[i].pos-npos;
40         while (P-d<0)
41         {
42             if (pque.empty())
43             {
44                 cout<<-1<<endl;
45                 return;
46             }
47             t++;
48             P+=pque.top();
49             pque.pop();
50         }
51         P-=d;
52         npos=sta[i].pos;
53         pque.push(sta[i].oil);
54     }
55     cout<<t<<endl;
56     return;
57 }
58 
59 int main()
60 {
61     input();
62     doit();
63     return 0;
64 }