题目描述

你需要驾驶一辆汽车行驶 L 单位距离。

最开始时, 卡车上有 P 单位的汽油。

汽车每开 1 单位距离需要消耗 1 单位的汽油。

如果在途中车上的汽油耗尽, 车就无法继续前行, 因而无法达到终点。

在途中一共有 N 个加油站。第ii 个加油站在距离 终点 A_i单位距离的地方, 最多可以给汽车加 B_i单位汽油。

假设卡车的燃油箱的容量是无限大的。问最少加多少次汽油可以达到终点 ？

无法达到请输出-1。

输入
第一行是 N，表示有多少个加油站
接下来 N 行，每行两个整数 A_i, B_i，表示每个加油站距离 终点 的位置，以及最多可以加多少油
最后一行是 L, P
1≤N≤2∗10^4
1≤L≤10^6
1≤P≤10^6
1≤Ai≤L
1≤Bi≤100
输出
一个整数，表示最少加多少次油
样例 1
输入
4
4 4
5 2
11 5
15 10
25 10
输出
2

解答
本题目使用贪心算法,首先在已有的油的情况下，尽可能走远。如果油不足以达到终点或者 下一个点。从已经经过的点中选取一个加油。 由于要求加油次数最小，那么在可选择的加油站中选择可加油最多的站点加油。(同样是加一次油，贪心选择加油最多的站点，这样可以将加油次数的可能降低到最低)

算法1

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using  namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>> q;

int n;
const int N = 20010;
pair<int, int> dat[N];
int l, p;

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> dat[i].first >> dat[i].second;
	}
	cin >> l >> p;

	sort(dat,dat+n);

	int currpos = l - p;   
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (currpos <= 0) { break; }
		if (currpos <= dat[i].first) {
			q.push({ dat[i].second,dat[i].first });
		}
		else {
			while (currpos > dat[i].first && !q.empty()) {
				currpos -= q.top().first; q.pop(); ans++;
			}
			if (currpos > dat[i].first) { break; }
			else{ q.push({ dat[i].second,dat[i].first }); }
		}
	}


	while (currpos > 0 && !q.empty()) {
		currpos -= q.top().first; q.pop(); ans++;
	}

	if (currpos <= 0) {
		cout << ans<< endl;
	}
	else {
		cout << -1 << endl;
	}
	
	return 0;
}

我的视频题解空间