首页 > 代码库 > POJ 3190 Stall Reservations(贪心+优先队列优化)
POJ 3190 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 |
额,贪心题=。=,STL里的优先队列
贪心策略:对奶牛挤奶开始时间由大到小排序,这样保证不会考虑有奶牛的开始挤奶时间在前面;
对入队的元素按挤奶结束时间时间由小到大排序,这样保证第一次就可以判定用不用添加槽=。=
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> #include<queue> using namespace std; const int maxn=1000000+10; struct node{ int st,ed; int pos;//pos记录是第几个奶牛 bool operator<(const node &a)const { if(ed==a.ed) return st>a.st; return ed>a.ed; } }a[maxn]; int used[maxn];//used记录奶牛挤奶的位置=。= int cmp(node l1,node l2) { if(l1.st==l2.st) return l1.ed<l2.ed; return l1.st<l2.st; } int main() { int n; while(~scanf("%d",&n)) { priority_queue<node>q; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].st,&a[i].ed); a[i].pos=i; } sort(a+1,a+n+1,cmp); q.push(a[1]); int ans=1; used[a[1].pos]=1; for(int i=2;i<=n;i++) { if(!q.empty()&&q.top().ed<a[i].st)//判定是否符合条件 { used[a[i].pos]=used[q.top().pos]; q.pop(); } else//不符合条件槽的数量加一,同时这个奶牛应该在新加的槽 { ans++; used[a[i].pos]=ans; } q.push(a[i]); } printf("%d\n",ans); for(int i=1;i<=n;i++) printf("%d\n",used[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。