poj 3190 优先队列+贪心

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

题意：

有n头牛，分别给他们挤奶的时间。

然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。

问最少需要多少个stall，并输出每头牛所在的stall。

e.g 样例：

INPUT:

5
1 10
2 4
3 6
5 8
4 7

OUTPUT:

4
1
2
3
2
4

HINT:

Explanation of the sample:

Here's a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..Stall 3 .. .. c3>>>>>>>>> .. .. .. ..Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

解析：

先将这些时间按照起始时间从小到大排序，然后用优先队列建立一个终止时间从小到大的堆。

每次比较堆顶，即终止时间最小的时间，与当前点起始时间的大小。

若小，则将当前这只牛加入到豪华午餐中。。。加入到堆顶这只牛的stall中。

若大，则自己另起炉灶，建立stall。

代码：

#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 maxn = 5e4 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);struct Node
{int st, ed;int id;bool operator < (const Node a) const{if (a.ed == ed)return a.st < st;return a.ed < ed;}
} cow[maxn];
int stall[maxn];bool cmp(Node a, Node b)
{if (a.st == b.st)return a.ed < b.ed;return a.st < b.st;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint n;while (~scanf("%d", &n)){memset(stall, 0, sizeof(stall));for (int i = 0; i < n; i++){scanf("%d%d", &cow[i].st, &cow[i].ed);cow[i].id = i;}sort(cow, cow + n, cmp);///按照起点排序priority_queue<Node> q;///按照终点建堆q.push(cow[0]);int cnt = 1;stall[cow[0].id] = 1;for (int i = 1; i < n; i++){if (!q.empty() && q.top().ed < cow[i].st){stall[cow[i].id] = stall[q.top().id];q.pop();q.push(cow[i]);}else{cnt++;stall[cow[i].id] = cnt;q.push(cow[i]);}}printf("%d\n", cnt);for (int i = 0; i < n; i++){printf("%d\n", stall[i]);}}return 0;
}

这篇关于poj 3190 优先队列+贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---