> 请问O（n^2）怎么做？
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）怎么做？ (1382) O1943 2006-10-03 11:01:17
  • Re:请问O（n^2）怎么做？ (23) wywcgs 2006-10-03 11:03:14
• Re:不懂。。 (73) Acsaga 2007-02-07 15:30:27
  • 这提示我也没看懂:( (79) Iamjw 2007-02-07 15:41:58
    • Re:这提示我也没看懂:( (46) yingzi 2007-03-11 23:18:34
      • Re:这提示我也没看懂:( (41) yingzi 2007-03-11 23:33:22