HBC24867XTL'sChessboard(评测),思维[USACO 2009 Dec S]Selfish Grazing题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Each of Farmer John's N (1

Each of Farmer John's N (1 <= N <= 50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number line. Cow i's favorite grazing range starts at location Si and ends at location Ei (1 <= Si < Ei; Si < Ei <= 100,000,000). Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows i and j can only graze at the same time if either Si >= Ej or Ei <= Sj. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences. Consider a set of 5 cows with ranges shown below: ... 1 2 3 4 5 6 7 8 9 10 11 12 13 ... ... |----|----|----|----|----|----|----|----|----|----|----|----|---- Cow 1: <===:===> : : : Cow 2: <========:==============:==============:=============>: Cow 3: : <====> : : : Cow 4: : : <========:===> : Cow 5: : : <==> : : These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively. For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24867XTL'sChessboard(评测) 思维[USACO 2009 Dec S]Selfish Grazing题解