HBC24741斐波,组合数学,数据结构,线段树Soda Machine题解

回忆凄美了谁 算法基础篇 77 0
全网最全C++题库,助您快速提升编程技能!题库丰富多样,涵盖各个领域,让您在练习中不断成长!
To meet the ever-growing demands of his N (1

To meet the ever-growing demands of his N (1 <= N <= 50,000) cows, Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine. The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in the range A_i..B_i A i ​ ..B i ​ (1<= A_i A i ​ <= B_i B i ​ ; A_i A i ​ <= B_i B i ​ <= 1,000,000,000) (a range that includes its endpoints), and FJ can place the soda machine at any integer point in the range 1..1,000,000,000. Since cows are extremely lazy and try to move as little as possible, each cow would like to have the soda machine installed within her grazing range. Sadly, it is not always possible to satisfy every cow's desires. Thus FJ would like to know the largest number of cows that can be satisfied. To demonstrate the issue, consider four cows with grazing ranges 3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing ranges: 1 2 3 4 5 6 7 8 9 10 11 12 13 |---|---|---|---|---|---|---|---|---|---|---|---|-... aaaaaaaaa bbbbbbbbbbbbbbbbb ccccc ddddddddddddddddddddd As can be seen, the first, second and fourth cows share the point 5, but the third cow's grazing range is disjoint. Thus, a maximum of 3 cows can have the soda machine within their grazing range.

HBC24741斐波,组合数学,数据结构,线段树Soda Machine题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: HBC24741斐波 组合数学 数据结构 线段树Soda Machine题解