题意：
开车前往一个距离为l的城市，途中有n个加油站，每行驶一个单位的距离就会消耗一个单位的汽油，每到一个加油站都可以加油，问是否能到达目的地，能到达的话，最少需要加多少次油。
思路：
衷心提醒大家仔细看题！！！！！！
输入的距离不是距起点的距离，而是距终点的距离(白WA3发血亏），而且不一定按顺序给出，需要进行排序，所以用结构体还是比较方便的。
我们可以这样想，既然路过的每个加油站都可以加油，意思就是“经过一个加油站就获得了在之后任何一个时间加油的权力”。
为了最小化加油的次数，我们只有在必须加油的时候才加油，并且加油的量应该是途径的所有加油站的可加油量的最大值。那么什么时候是必须加油的时候呢？
显然 当前油箱里的油不够前往下一个加油站时我们必须加油，且应该选加油量最大的加油站加油
所以我们用优先队列存储我们经过的所有加油站的可加油量，问题即可得解。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<map> #include<vector> #include<set> #include<map> #include<algorithm> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 2e4 + 10; struct node { int dis, u; }sta[maxn]; bool cmp(node a, node b) { return a.dis < b.dis; } int main() { int n;cin >> n; for (int i = 1;i <= n;++i) { int x, y;cin >> x >> y; sta[i].dis = x;//距终点的距离 sta[i].u = y;//可加油的量 } int l, p;cin >> l >> p; //求加油站到起点的距离 for (int i = 1;i <= n;++i) { sta[i].dis = l - sta[i].dis; } sort(sta + 1, sta + n + 1, cmp);//排序 //将终点看成最后一个不能加油的加油站 sta[n + 1].dis = l; sta[n + 1].u = 0; priority_queue<int>pq; int ans = 0;//加油次数 int pos = 0;//当前位置 int oil = p;//油箱里的油 for (int i = 1;i <= n + 1;++i) { //前往下一个加油站的距离 int t = sta[i].dis - pos; //油量不够时，从优先队列中加油 while (t > oil) { //如果在途中优先队列为空 说明无法到达目的地 if (pq.empty()) { puts("-1"); return 0; } oil += pq.top(); pq.pop(); ++ans; } oil -= t; pos = sta[i].dis; pq.push(sta[i].u);//获得可加油的权力 } printf("%d\n", ans); return 0; }
