reservations专题

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

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

Stall Reservations POJ - 3190(贪心+STL)

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

[BZOJ1651] [Usaco2006 Feb]Stall Reservations 专用牛棚

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1651 题目大意 给出奶牛运动的时间段,询问同一时间最多的奶牛数 题解 线段树或差分序列 线段树 varx:array[0..3000000,1..4]of longint;i,j,k:longint;n,a,b,m:longint;function max(a,b:longi