#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;
}
poj 2431 优先级队列
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
推荐阅读更多精彩内容
- 解决方案 下面的类利用 heapq 模块实现了一个简单的优先级队列: 下面使用 仔细观察可以发现,第一个 pop(...
- (2017-09-30-星期六 17:13:12) which only defines the size of ...
- 最近工作中有这么一种需求,需要定时将三种任务(假设任务为:A、B、C)分配到10台Windows Server中执...