HBC24111背包,组合数学,数学,生成函数[USACO 2016 Feb P]Load Balancing题解

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

Farmer John's N cows are each standing at distinct locations … on his two-dimensional farm . FJ wants to partition his field by building a long north-south fence with equation x=a . He also wants to build a long east-west fence with equation y=b, where b is an even integer. These two fences cross at the point (a,b), and together they partition his field into four regions.FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting M be the maximum number of cows appearing in one of the four regions, FJ wants to make M as small as possible. Please help him determine this smallest possible value for M.

Farmer John's N cows are each standing at distinct locations (x1,y1)…(xn,yn) on his two-dimensional farm (1≤N≤100,000, and the xi's and yi's are positive odd integers of size at most 1,000,000). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=a (a will be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y=b, where b is an even integer. These two fences cross at the point (a,b), and together they partition his field into four regions. FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting M be the maximum number of cows appearing in one of the four regions, FJ wants to make M as small as possible. Please help him determine this smallest possible value for M.

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC24111背包 组合数学 数学 生成函数[USACO 2016 Feb P]Load Balancing题解