HBC24735道路铺设,堆/优先队列,贪心[USACO 2010 Mar G]Barn Allocation题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures.

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures. The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered 1..N; stall i has capacity C_i C i ​ cows (1 <= C_i C i ​ <= 100,000). Cow i may request a contiguous interval of stalls (A_i, B_i) (A i ​ ,B i ​ ) in which to roam (1 <= A_i A i ​ <= N; A_i A i ​ <= B_i B i ​ <= N), i.e., the cow would like to wander among all the stalls in the range A_i..B_i A i ​ ..B i ​ (and the stalls must always have the capacity for her to wander). Given M (1 <= M <= 100,000) stall requests, determine the maximum number of them that can be satisfied without exceeding stall capacities. Consider both a barn with 5 stalls that have the capacities shown and a set cow requests: Stall id: 1 2 3 4 5 +---+---+---+---+---+ Capacity: | 1 | 3 | 2 | 1 | 3 | +---+---+---+---+---+ Cow 1 XXXXXXXXXXX (1, 3) Cow 2 XXXXXXXXXXXXXXX (2, 5) Cow 3 XXXXXXX (2, 3) Cow 4 XXXXXXX (4, 5) FJ can't satisfy all four cows, since there are too many requests for stalls 3 and 4. Noting that Cow 2 requests an interval that includes stalls 3 and 4, we test the hypothesis that cows 1, 3, and 4 can have their requested stalls. No capacity is exceeded, so the answer for this set of data is 3 -- three cows (1, 3, and 4) can have their requests satisfied.

标签： HBC24735道路铺设 堆/优先队列 贪心[USACO 2010 Mar G]Barn Allocation题解