POJ2431.Expedition

这道题大意是说有一个起点 S，终点 E，在这其中有 N 个加油站，每个加油站可以加的油量，以及起点到加油站之间的距离。求到达终点的最少停靠次数，如果无法到达返回 - 1

贪心规律展开目录

何时加油最合适？没油的时候加油最合适；在哪个加油站加油最合适？在油量最多的加油站加油最合适

思路展开目录

1. 设置一个最大堆，用来存储经过加油站的汽油量
2. 按照从起点至终点的方向，遍历各个加油站之间的距离
3. 每次需要走两个加油站之间的距离 d，如果发现汽油不够走距离 d 时，从最大堆中取出一个汽油量添加，直到可以足够走距离 d
4. 如果把最大堆的汽油都添加仍让不够行进距离 d，则无法达到重点
5. 当前油量 p 减少 d
6. 将当前加油站油量添加至最大堆

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool cmp(pair<int,int> &a,pair<int,int> &b) {
    return a.first > b.first;
} 
int get_minimum_stop(int L,int P,vector<pair<int,int>> &stop) {//L为起点到终点的距离，P为起始油量 
    priority_queue<int> Q;//存储油量的最大堆
    int result = 0;
    stop.push_back(make_pair(0,0));
    sort(stop.begin(),stop.end(),cmp);
    for(int i = 0;i < stop.size();i++) {
        int dis = L - stop[i].first;
        while(!Q.empty() && P < dis) {
            P += Q.top();
            Q.pop();
            result++;
        }
        if(Q.empty() && P < dis) {
            return -1;
        }
        P = P - dis;
        L = stop[i].first;
        Q.push(stop[i].second);
    }
    
    
    
    return result;
}
int main() {
    vector<pair<int,int>> stop;
    int N,L,P,distance,fuel;
    scanf("%d",&N);
    for(int i = 0;i < N;i++) {
        scanf("%d %d",&distance,&fuel);
        stop.push_back(make_pair(distance,fuel));
    } 
    scanf("%d %d",&L,&P);
    printf("%d\n",get_minimum_stop(L,P,stop));
    return 0;
}