为什么前文中说sort by AH+BW
可是伪代码中的loop却又说是 minw in increase order
这个是矛盾还是我理解错了？
谢谢

> ANALYSIS by Bruce Merry (South Africa) ==============================
> 
> The following simple algorithm will work, but will be too slow on
> the big cases:
> 
> Loop over all weights and all heights in the set, and consider the
> loop variables to be the minimum weight and height. In this, loop
> over all cows and count the number that meet the minimum weight and
> height and fit the constraint.
> 
> This is O(n^3), which will be too slow for N = 1000.
> 
> We can refine this algorithm by building things up. Suppose we fix minh
> and loop through the possibilities for minw in increasing order. As
> minw increases, the set of points satisfying the linear constraint gets
> strictly bigger. If we sort the points by Ah + Bw, then they will
> become valid points in the order they appear (valid in the sense of the
> linear constraint, not relative to minw or minh). Thus we can use the
> following algorithm:
> 
> - Loop over minh
>   - Loop over minw in increasing order
>     - add new points to the set of valid points, keeping track of the
>       last one added (for next time round the loop)
>     - compare the count to the best so far
>     - remove the point corresponding to minw from the set
> 
> This is now an O(n^2) algorithm, easily fast enough.

• Re:请问O（n^2）怎么做？ (23) wywcgs 2006-10-03 11:03:14