POJ 2431 （优先队列）

佚名 5年前 (2019-03-31) 算法 1494人围观抢沙发百度已收录

题目链接：https://vjudge.net/problem/POJ-2431

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：

　　“ 在卡车行驶途中，只有经过加油站才能加油。” 我们不妨转变思路，理解成“当卡车驶过加油站时就获得了加油的权利”，在之后需要加油时，就认为是在之前经过加油站时加的油即可。

　　那么我们何时加油呢，最好的办法当然是选择能加最多油的加油站了（选择一次加大量的油，可以减少加油次数），这时就要用到优先队列了。

　　下面是代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct gas
 8 {
 9     int dis;
10     int fule;
11 }a[10005];
12 
13 bool cmp(gas A, gas B)
14 {
15     return A.dis<B.dis;
16 }
17 
18 priority_queue<int> que; 
19 
20 int main()
21 {
22     int n,L,P;
23     cin>>n;
24     for(int i=0; i<n; i++)
25     {
26         cin>>a[i].dis>>a[i].fule;
27     }
28     cin>>L>>P;
29     for(int i=0; i<n; i++)
30     {
31         a[i].dis = L-a[i].dis;
32     }
33     sort(a, a+n, cmp);
34     a[n].dis=L;
35     a[n].fule=0;
36     n++;//关键 
37     int position=0, count=0, tank=P;//所在位置, 加油次数, 剩余油量 
38     for(int i=0; i<n; i++)
39     {
40         int d=a[i].dis - position;
41         while(tank-d<0)
42         {
43             if(que.empty())
44             {
45                 puts("-1");
46                 return 0;
47             }
48             tank += que.top();//加油
49             que.pop();
50             count++; 
51         }
52         tank -= d;
53         position = a[i].dis;
54         que.push(a[i].fule);//关键 
55     }
56     cout<<count<<endl;
57     
58     return 0;
59 }