3190专题

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 3190 贪心 + 优先队列优化

对cow进行排列。按L以及R从小到大排序。确保遍历的时候优先取到最小的L. 然后就可以对cow遍历求解。 #include <iostream>#include <queue>#include <algorithm>#include<functional>using namespace std;struct N{int l,r,id,stall;bool operator <(

[POJ 3190] Stall Reservations (区间贪心)

POJ - 3190 给定若干个区间,问至少要分成几组 使得同组的区间互不重叠 典型的区间贪心问题 贪心的策略就是对左端点排序,然后依次选择安排 记录一下每个隔间最右端点的位置,然后用最小堆维护一下 当前区间尽可能地放到最右点最小的组里 如果这组依旧放不进去,就没有隔间能放得进去了 所以就要为其申请一个新的隔间 否则就把它安排到这个隔间里,并且更新此隔间最右端点 #p

Stall Reservations POJ - 3190(贪心+STL)

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