首页 > 代码库 > poj3190Stall Reservations(贪心+优先队列)
poj3190Stall Reservations(贪心+优先队列)
题目链接:
啊哈哈,点我点我
思路:
首先根据挤奶时间的先后顺序排序。。。然后将第一头牛加入优先队列。。然后就是加入优先队列的牛应该根据越早结束挤奶那么优先级更高,如果时间结束点相等,那么开始时间早的优先级高。。。
然后从前向后枚举。如果碰到有牛的挤奶时间的开始值大于优先队列的首部的结束值,那么说明这两头牛可以一起公用一个挤奶房。。然后从优先队列中删除这头牛。。那么这个问题就得到解决了。。。
题目:
Language: Stall Reservations
Description Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. Help FJ by determining:
Input Line 1: A single integer, N Lines 2..N+1: Line i+1 describes cow i‘s milking interval with two space-separated integers. Output Line 1: The minimum number of stalls the barn must have. Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period. Sample Input 5 1 10 2 4 3 6 5 8 4 7 Sample 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 10 Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>> Stall 2 .. c2>>>>>> c4>>>>>>>>> .. .. Stall 3 .. .. c3>>>>>>>>> .. .. .. .. Stall 4 .. .. .. c5>>>>>>>>> .. .. ..Other outputs using the same number of stalls are possible. Source USACO 2006 February Silver |
代码为:
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn=50000+10; int order[maxn]; struct Node { int st,en,pos; friend bool operator<(Node a,Node b) { if(a.en==b.en) return a.st<b.st; return a.en>b.en; } }node[maxn]; bool cmp(Node a,Node b) { if(a.st==b.st) return a.en<b.en; else return a.st<b.st; } priority_queue<Node>Q; int main() { int n,ans; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d%d",&node[i].st,&node[i].en); node[i].pos=i; } sort(node+1,node+1+n,cmp); ans=1; Q.push(node[1]); order[node[1].pos]=1; for(int i=2;i<=n;i++) { if(!Q.empty()&&Q.top().en<node[i].st) { order[node[i].pos]=order[Q.top().pos]; Q.pop(); } else { ans++; order[node[i].pos]=ans; } Q.push(node[i]); } printf("%d\n",ans); for(int i=1;i<=n;i++) printf("%d\n",order[i]); while(!Q.empty()) Q.pop(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。