首页 > 代码库 > POJ2431（优先队列）
POJ2431（优先队列）
好吧，最近终于开始看点算法了，但还是停留在水题阶段：）
所以准备更新下看到的有意思的题（参考书籍：挑战程序竞赛 第二版）
这道题题目就不管了，我是先做了，又参考了下书上的解法，所以应该没有问题。
这道题是利用数据结构中的优先队列完成的。。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。本来优先队列应该是将数据插入队列后较小数据优先级高。 但C++中的优先队列为较大的元素优先级高，但这好像让这道题更容易了点。。。
其他的注意应该就是这道题的输入要注意一点。接下来贴一下源码。
1 #include <iostream>
2
3 #include <cstdio>
4
5 #include <algorithm>
6
7 #include <queue>
8
9 using namespace std;
10
11 typedef pair<int, int> R;
12
13 int N, L, P;
14
15 R A[1000005];//用pair型存一下每个加油点到起点的距离及相应油量
16
17 void solve() {
18
19 int sumo = P; //从开始能向前走的距离
20
21 int count = 0;
22
23 priority_queue<int> que; //使用优先队列实现每次油量不足时取得存入的最大油量
24
25 for (int i = 0; i <= N; i++) {
26
27 while (sumo < A[i].first) {
28
29 if (que.empty()) {
30
31 puts("-1");
32
33 return;
34
35 }
36
37 else {
38
39 sumo += que.top();
40
41 que.pop();
42
43 count++;
44
45 }
46
47 }
48
49 que.push(A[i].second);
50
51 }
52
53 cout << count << endl;
54
55 }
56
57
58 bool cmp(const R &a, const R &b) {
59
60 return a.first < b.first;
61
62 }
63
64
65
66 int main() {
67
68 cin >> N;
69
70 for (int i = 0; i < N; i++) {
71
72 cin >> A[i].first >> A[i].second;
73
74 }
75
76 cin >> L >> P;
77
78 for (int i = 0; i<N; i++)
79
80 {
81
82 A[i].first = L - A[i].first;
83
84 }
85
86 A[N] = R(L,0);
87
88 sort(A, A + N, cmp);
89
90 solve();
91
92 return 0;
93
94 }
POJ2431（优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。