POJ2431-最优队列（最小堆）解法

这道题有一个坑，就是给出的加油站到终点的距离不一定是降序排列好了的。

所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>下的sort函数，对pair<int,int>类型的输入进行排序，非基本类型的数据排序需要重写sort函数的第三个参数。

源代码

#include<queue>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> p;

bool comp(p p1,p p2)
{
    return p1.first<p2.first;
}

int main()
{
    int N,P,L;
    cin>>N;

    vector<p> input;
    int a,b;
    for(int i=N-1;i>=0;i--)
    {
        cin>>a>>b;
        pair<int,int> mm = make_pair(a,b);
        input.push_back(mm);

    }
    cin>>L>>P;

    sort(input.begin(),input.end(),comp);

    int counter=0;
    int go=0;
    priority_queue<int> gas;
    int i=0;
    while(go<L)
    {

        go+=P;
        if(go<L)
        {
            P=0;
            while(!input.empty()&&L-input.back().first<=go)
                {
                    gas.push(input.back().second);
                    input.pop_back();
                    }
                    if(gas.empty())
                        {
                            cout<<-1<<endl;
                            return -1;
                        }
                    P+=gas.top();
                    gas.pop();
                    counter++;

        }

    }
    cout<<counter<<endl;
    return counter;

}