M02431: Expedition

heap,greedy, http://cs101.openjudge.cn/practice/02431/

【姚博骞 25物院】思路：构建一个堆，永远只吃堆里面最多的那个 其实有点后悔贪心的想法。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int main()//greedy heap
{
    int n;
    cin>>n;
    vector<pair<int,int>> stop;
    for(int i=0;i<n;i++)
    {
        int p,q;
        cin>>p>>q;
        stop.push_back({p,q});
    }
    int l,p;
    cin>>l>>p;
    sort(stop.begin(),stop.end(),[](pair<int,int> &a,pair<int,int> &b){
        return a.first>b.first;
    });
    priority_queue<int> pq;//大顶堆；
    int ans=0;
    int i=0;
    int dist=l-p;
    while(i<n&&dist>0)
    {
        while(i<n&&stop[i].first>=dist)
        {
            pq.push(stop[i].second);
            i++;
        }
        if(pq.empty()) break;
        dist-=pq.top();
        pq.pop();
        ans++;
    }
    if(dist<=0)
    {
        cout<<ans;
    }
    else
    {
        cout<<-1;
    }
    return 0;
}