MENU

POJ2431.Expedition

July 5, 2018 • Read: 2971 • 算法阅读设置


这道题大意是说有一个起点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;
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code