首页 > 代码库 > 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:
Help FJ by determining:
- The minimum number of stalls required in the barn so that each cow can have her private milking period
- An assignment of cows to these stalls over time
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.
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.
Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.
Sample Input
51 102 43 65 84 7
Sample Output
412324
Hint
Explanation of the sample:
Here‘s a graphical schedule for this output:
Here‘s a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10Other outputs using the same number of stalls are possible.
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..
题意:奶牛要在指定的时间挤奶,一台机器只能给一头奶牛挤奶,问最少要几台机器。
思路:用STL里的优先队列,判断空闲机器是否满足下一头奶牛的挤奶时间,满足就让挤完奶的奶牛出队把机器编号给下一头奶牛,下一头奶牛入队,否则机器+1,下一头奶牛入队.
注意:输出的顺序和输入的顺序相同,在输入的时候把下标一起存入结构体,另外开一个数组记录机器的编号,在排序后下标就不会乱了。
ac代码:
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 #include<queue> 6 using namespace std; 7 struct node 8 { 9 int a;10 int b;11 int c;12 bool operator<(const node &c)const13 {14 if(b==c.b)15 return a>c.a;16 return b>c.b;17 }18 } d[60000];19 priority_queue<node> q;20 int s[60000];21 bool cmp(struct node a,struct node b)22 {23 if(a.a==b.a)24 return a.b<b.b;25 return a.a<b.a;26 }27 int main()28 {29 int a,b,i,j,n=1;30 scanf("%d",&a);31 for(i=1; i<=a; i++)32 {33 scanf("%d%d",&d[i].a,&d[i].b);34 d[i].c=i;35 }36 sort(d+1,d+a+1,cmp);37 q.push(d[1]);38 s[d[1].c]=1;39 for(i=2; i<=a; i++)40 {41 int x=q.top().b;42 if(x<d[i].a)43 {44 s[d[i].c]=s[q.top().c];45 q.pop();46 }47 else48 {49 n++;50 s[d[i].c]=n;51 }52 q.push(d[i]);53 }54 printf("%d\n",n);55 for(i=1; i<=a; i++)56 printf("%d\n",s[i]);57 }
有什么问题可以评论提问。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。