Stall Reservations POJ - 3190（贪心+STL）

本文主要是介绍Stall Reservations POJ - 3190（贪心+STL），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

真得好好反思一下了，这么简单的一道贪心题竟然wa了12次！
这道题就是一道简单的时间调度问题，首先用到一个优先队列priority_queue来保存的是牛圈，优先级是按牛圈开始空闲的时间从小到达排序的（这个STL不大会用百度的orz）。然后就是把牛排序，先产奶的放前面如果产奶开始时间相同那么就把结束时间在前面的放到前面。
模拟一下就行了，这种题呀，wa了就不要瞎改了照着样例自己推一遍诶。

#include <queue>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;struct cow {int num;  // 牛的编号int b;int e;int w;    // 在哪个地方
} p[50010];struct stall {int b;int num;stall(int b, int num) : b(b), num(num) {}   // 构造函数初始化bool operator < (const stall &a) const {return b > a.b;  //最小值优先}
};bool cmp(cow a, cow b) {if (a.b == b.b) {return a.e < b.e;}return a.b < b.b;
}
bool cmp1(cow a, cow b) {return a.num < b.num;
}int main() {freopen("input.txt", "r", stdin);int n;while(~scanf("%d", &n)) {if (n == 0) { printf("0\n"); continue; }priority_queue<stall> beg;beg.push(stall(1, 1));int ans = 1;for(int i = 0; i < n; i++) {scanf("%d%d", &p[i].b, &p[i].e);p[i].num = i + 1;}sort(p, p+n, cmp);for(int i = 0; i < n; i++) {stall t = beg.top();if (t.b <= p[i].b) {t.b = p[i].e + 1;beg.pop();beg.push(t);p[i].w = t.num;}else {ans++;p[i].w = ans;beg.push(stall(p[i].e + 1, ans));}}sort(p, p+n, cmp1);printf("%d\n", ans);for(int i = 0; i < n; i++) {printf("%d\n", p[i].w);}}return 0;
}