贪心，优先队列

题目链接：http://poj.org/problem?id=2431

题目大意：

一辆卡车，初始时，距离终点L，油量为P，在起点到终点途中有n个加油站，每个加油站油量有限，而卡车的油箱容量无限，卡车在行车途中，每走一个单位的距离消耗一个单位的油量，给定n个加油站距离终点的距离以及油存储量。问卡车是否能到达终点，如果可达，最少需要加多少次油，否则输出-1.

题目思路：

采用贪心的思想，卡车当然在不加油的情况下走的越远越好了，而当它没油时，我们再判断卡车在经过的途中的加油站，哪个加油站加的油最多，选油量最多的，这样后面加油次数也越少，然后又继续行驶，当它又没油了的时候，继续选它从起点到该点所经过的加油站油量最多的加油。

做法先将加油站到终点的距离由远到近排下序，这样离起点就是由近到远。就是每经过一个加油站就将该加油站的油量压入优先队列中，然后每次没油的时候，去队首元素加油即可。

参考：https://www.cnblogs.com/zjl192628928/p/9414201.html

为什么这样做呢，经过加油站后还可以加油？其实不是这样的，只是预先模拟汽车到达那个加油站的情况，并不是汽车真正到达那个加油站，这样才能预算沿途究竟在哪个加油站加油最好。之前纠结这个有点久2333，后来就想想这个只是预想汽车到达那个加油站，并没有真正到达

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
	Submit Time:2018-09-29 12:18:22
	Time:172MS
	Memory:300K
*/
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 1E6;
//代表一个加油站，x代表距离终点位置，y代表能加的油量
struct node 
{
    int x, y;
}stru[MAXN];


bool cmp(node x1, node x2)
{
    return x1.x < x2.x;
}

int main()
{
    ios::sync_with_stdio(false);
    int p, l, n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> stru[i].x >> stru[i].y;
    cin >> p >> l;

    //因为给的是距离终点的距离，不是距离起点，所以得算出距离起点的
    for(int i = 0; i < n; i++)
        stru[i].x = p - stru[i].x;
    
    //将终点也看是一个加油站，避免一些特殊情况，比如
    /*
    0
    3 1
    */
    stru[n].x = p;
    stru[n].y = 0;
    n++;
    sort(stru, stru + n, cmp); //因为题目不一定按顺序输入，所以得手动排序，将离起点最近的放在前面

    priority_queue<int>pq;
    int ans = 0, pos = 0, tank = l; //ans:加油次数，pos：现在所在位置，tank：油箱中的汽油量

    for(int i = 0; i < n; i++) //模拟经过所有加油站
    {
        int d = stru[i].x - pos; //到下一个加油站需要的路程
        while(tank - d < 0) //到不了了，需要在沿途加油
        {
            if(pq.empty()) //没有加油站可以加油，输入-1，代表到达不了
            {
                puts("-1");
                return 0;
            }
            tank += pq.top(); //否则找个加油站，加最多的油，正好优先队列第一个元素就是最大值
            pq.pop(); 
            ans++;
        }

        tank -= d; //如果到达的了这个加油站，说明油够，不需要加，那么只需要减去到达这个加油站的油量就行了
        pos = stru[i].x; //位置更新为这个加油站
        pq.push(stru[i].y); 
    }
    cout << ans;
    return 0;
}