poj 2431 优先级队列

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = 10000;
int N, L, P;

struct stop{
    int dist, fuel;
};

stop position[MAX_N + 10];

bool cmp(const stop &a, const stop &b) {
    return a.dist > b.dist;
}

void solve() {
    priority_queue<int> que;
    int ans = -1;   //将原有的P放入了que中,所有多计算了一次,故此预设为 -1
        que.push(P);
        int index = 0;
        while(L > 0 && !que.empty())
        {
            ans++;
            int tmp = que.top();
            que.pop();
            L -= tmp;
            while(index < N && L <= position[index].dist)
                que.push(position[index++].fuel);
        }
        printf("%d\n", L <= 0? ans: -1);  
}

int main() {
    while(scanf("%d", &N) != EOF) {
        
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &position[i].dist, &position[i].fuel);
        }
        scanf("%d %d", &L, &P); 
        sort(position, position + N, cmp);
        solve();
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容