POJ3614与优先队列

2023-11-11 12:33

文章标签 队列优先 poj3614

本文主要是介绍POJ3614与优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

优先队列这个博主讲的比较全

题意：
奶牛晒太阳，有下限和上限，要保证晒到上下限之间，每瓶防晒霜可以固定一头奶牛晒到一个固定值，求最多几头奶牛可以达到要求

要点;
先把奶牛按照最小值从小到大排序，在把防晒霜从小到大排序，从最小的防晒霜枚举，如果大于奶牛的最小值就把奶牛的最大值放入优先数列（从小到大），这样的话每次只要比较优先数列的第一项与奶牛的最大值就可以了。这里面也有贪心的思想，每次防晒霜优先涂最大值比较小的奶牛。

代码如下：

#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <cstdio>  
#include <map>  
#include <vector>  
#include <queue>  
#define maxn 3000
using namespace std;
struct node
{int min;int max;
};
node cow[maxn], bot[maxn];bool cmp(node a, node b)
{if (a.min == b.min)return a.max < b.max; //bool型这里一定要用<,不能用-return a.min < b.min;
}struct cmp_temp  //结构体控制优先队列小的数优先度高
{bool operator()(int x, int y){return x > y;  //注意这里是大于}
};
priority_queue<int, vector<int>, cmp_temp>que; //优先队列的定义函数声明
int main()
{int c, l, i, j, cur, ans;while (scanf("%d%d", &c, &l) != EOF){for (i = 0; i < c; i++)scanf("%d%d", &cow[i].min, &cow[i].max);for (i = 0; i < l; i++)scanf("%d%d", &bot[i].min, &bot[i].max);sort(cow, cow + c, cmp);sort(bot, bot + l, cmp); //先从小到大排序cur = ans = 0;for (i = 0; i < l; i++){while (cur<c&&cow[cur].min <= bot[i].min){que.push(cow[cur].max); //将符合条件的奶牛的最大值放入优先队列cur++;}while (bot[i].max&&que.size())//确保防晒霜没用完{if (bot[i].min <= que.top()){ans++;bot[i].max--; //防晒霜瓶数-1}que.pop();//不管符不符合队列中都有一个元素出队}}   printf("%d\n", ans);}return 0;
}