欲張りアルゴリズムの例題(五)

欲張りアルゴリズムの例題(五)
最良の給油方法のテーマの説明:1本の道路の上で知っていて、1つの起点と1つの終点があって、この間にnつのガソリンスタンドがあります;このn個のガソリンスタンドから終点までの距離dと各ガソリンスタンドが給油可能な量l、始点位置から終点までの距離Lと始点タンク中のガソリン量Pとが知られている.仮に1単位のガソリンを使ってすぐ1単位の距離を歩いて、ガソリンタンクはオンラインになっていないで、少なくとも何回の油をプラスして、起点から終点まで運転することができますか?(到着できなければ-1に戻る)考え:車はnのガソリンスタンドを通って、このnのガソリンスタンドに対して、どのガソリンスタンドで止まってガソリンを入れるべきで、最終的にゴールに着くことができて、またガソリンの回数を最小限に抑えることができますか?順番にガソリンスタンドを巡ると、あるガソリンスタンドで止まって給油する必要はないかもしれませんが、今回の給油をしなくてもゴールに着く可能性があります.もしあるガソリンスタンドで止まらずに給油したら、ガソリンが足りないためにゴールに着くことができないか、あるいは後ろでもっと何度も給油しなければゴールに着くことができないかもしれません.油量が一番多いガソリンスタンドで給油するのが最適です!アルゴリズムの構想:1、1つの最大の山を設置して、ガソリンスタンドを通るガソリンの量を貯蔵します2、起点から終点の方向によって、各ガソリンスタンドの間の距離を遍歴します3、毎回2つのガソリンスタンドの間の距離dを歩かなければならなくて、もしガソリンが距離dを歩かないことを発見するならば、最も大きい山の中から1つのガソリンの量を取り出して添加して、十分に距離d 4を歩くことができるまで、最も多くのガソリンを添加しても距離dが足りないと、終点5に達することができず、現在の油量pがd 6減少し、現在のガソリンスタンドの油量を最大炉に添加する

#include
#include
#include
#include
#include
#include
using namespace std;
bool comp(const pair<int, int>& p, const pair<int, int>& p1)
{
     
    return p.first > p1.first;
}
int function(int L,int P,vector<pair<int, int> >& stop)
{
     
    priority_queue<int> Q;
     int result = 0;
     stop.push_back(make_pair(0, 0));
     sort(stop.begin(), stop.end(), comp);
     
     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 -= dis;
         L = stop[i].first;
         Q.push(stop[i].second);

     }
}
int main()
{
      
    vector<pair<int, int>> stop;
    int N;
    int L;
    int p;
    int distance;
    int fuel;
    cin >> N;
    for (int i = 0; i < N; i++) {
     
        cin >> distance >> fuel;
        stop.push_back(make_pair(distance, fuel));
    }
    cin >> L >> p;
    cout << function(L, p, stop);

    return 0;
}