Description

一辆汽车要行驶 L 单位距离。最开始时，汽车上有 P 单位汽油，每向前行驶1单位距离消耗 1 单位汽油。如果在途中车上的汽油耗尽，汽车就无法继续前行，即无法到达终点。

途中共有 N 个加油站，加油站提供的油量有限，汽车的油箱无限大，无论加多少油都没问题。

给出每个加油站距离终点的距离 L 和能够提供的油量 P ，问卡车从起点到终点至少要加几次油？如果不能到达终点，输出 -1 。

Input

第一行输入 N ； 接下来 N 行分别输入两个整数 L 和 P 。 最后一行表示汽车的起点到终点的位置 L 和油量 P 。

样例一：

4
4 4
5 2
11 5
15 10
25 10

样例二：

4
4 4
5 2
11 5
15 10
25 1

Output

输出到达城镇所需的最少站点数，如果车无法到达城镇,则输出-1。

样例一：

2

样例二：

-1

Solution

货车有一个初始的可以走的距离，只要在这个距离内的加油站，它都可以停下来加油。

所以我们把能经过的加油站按照加油量从大到小排列，弱货车停了且没到达终点，那么从中依次取出最大的给货车加油。

然后货车继续向前走，将中间经过的加油站记录下来，重复该过程直到到达终点或者无法到达。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

struct node {
    int l,p;
}d[N];

bool cmp(node &a,node &b) {
    if(a.l != b.l) return a.l > b.l;
    else return a.p > b.p;
}

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0 ; i < n ; i ++ ) {
        cin >> d[i].l >> d[i].p;
    }
    
    sort(d,d+n,cmp);
    
    priority_queue<int,vector<int>,less<int> > q;
    
    int l,p;
    cin >> l >> p;
    
    int ans = 0;
    int now = p; // 当前剩的油量
    int pos = l; // 距离
    for (int i = 0 ; i < n ; i ++ ) {
        int distance = pos - d[i].l; // 距离最近加油站的距离
        while (distance > now) {
            if(q.size()) {
                int t = q.top();
                q.pop();
                now += t;
                ans ++ ;
            }
            else {
                cout << -1 << endl;
                return 0;
            }
        }
        
        now -= distance;
        pos = d[i].l;
        
        q.push(d[i].p);
    }
    
    cout << ans << endl;
    
    return 0;
}

加油站之最小加油次数 (15 分)

原文：https://www.cnblogs.com/Crystar/p/14827479.html