本文主要是介绍poj 2431 poj 3253 优先队列的运用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj 2431：
题意：
一条路起点为0， 终点为l。
卡车初始时在0点，并且有p升油，假设油箱无限大。
给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。
问最少加几次油可以到达终点，若不能到达，输出-1。
解析：
《挑战程序设计竞赛》：
“在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一次可以在之后任何位置加一次fuel[i]升油的机会”。
在解决问题上也可以这样做，之后需要加油时，认为在之前经过该加油站加的油就行了。
那么，因为希望到达终点时的加油次数尽量少，所以当燃料为0了之后再进行加油看上去是一个不错的方法。在燃料为0时，应该使用哪个加油站来加油呢？
显然，应该选择加油量fuel[i]最大的加油站。这里就用到了优先队列。”
所以，按题中，装换排序，用优先队列就行了。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 10000 + 10;
const double eps = 1e-9;int n, l, p;struct Node
{int x, fuel;bool operator<(Node a)const{return fuel < a.fuel;}
} node[maxn];bool cmp(Node a, Node b)
{return a.x < b.x;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 0; i < n; i++){scanf("%d%d", &node[i].x, &node[i].fuel);}scanf("%d%d", &l, &p);for (int i = 0; i < n; i++)node[i].x = l - node[i].x;sort(node, node + n, cmp);node[n].x = l;node[n++].fuel = 0;
// for (int i = 0; i < n; i++)
// {
// cout << node[i].x << " " << node[i].fuel << endl;
// }priority_queue<Node> q;
// q.push(node[0]);
// q.push(node[1]);
// q.push(node[2]);
// q.push(node[3]);
// cout <<endl;
// while (!q.empty())
// {
// cout << q.top().fuel << endl;
// q.pop();
// }bool flag = true;int pos = 0, ans = 0;for (int i = 0; i < n; i++){int d = node[i].x - pos;while (p < d){if (q.empty()){flag = false;break;}p += q.top().fuel;q.pop();ans++;}if (!flag)break;pos = node[i].x;p -= d;q.push(node[i]);}if (!flag)ans = -1;printf("%d\n", ans);}return 0;
}
poj 3253：
贪心+优先队列。
greater的运用。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 20000 + 10;
const double eps = 1e-9;int n;
int l[maxn];void solve()
{LL ans = 0;priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i < n; i++)q.push(l[i]);
// cout << n <<endl;
// cout << q.size() << endl;while (q.size() > 1){int l1, l2;l1 = q.top();q.pop();l2 = q.top();q.pop();
// cout << l1 << l2 << endl;ans += (LL)l1 + (LL)l2;q.push(l1 + l2);}printf("%lld\n", ans);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 0; i < n; i++)scanf("%d", &l[i]);solve();}return 0;
}
这篇关于poj 2431 poj 3253 优先队列的运用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
