> 用网络流写WA了，不知道是做法错了还是代码错了~~~郁闷ing 。。。哪位大牛过了的透露下八~~~
This problem is solvable by a simple greedy algorithm: consider the bottles of sunscreen in increasing order of SPF, and assign each one (if possible) to the cow having the lowest maxSPF rating. Why does this give an optimal solution? Let B denote a bottle of sunscreen with the lowest SPF rating. If no cow is compatible with B, then clearly B cannot be assigned in any solution, so we can ignore B. Otherwise, let C be the cow having lowest maxSPF rating that is compatible with B. We claim that there is always an optimal solution in which C is paired with B, so it is "safe" to make this assignment as our algorithm progresses (i.e., it will never make a wrong decision and end up in a situation where an optimal solution is no longer reachable). To see this, suppose there is an optimal solution S where C is _not_ paired with B, and consider a few cases: (i) C and B are both unassigned in S. This case cannot happen, since we could assign C with B and obtain an even better solution, contradicting the optimality of S. (ii) C is assigned in S but B is not. Here, by reassigning C to B, we obtain an equally-good solution in which C and B are assigned. (iii) B is assigned in S but C is not. Same as (ii), only we reassign B. (iv) C and B are both assigned in S. Let B' be the bottle assigned to C, and C' be the cow assigned to B. Here, you can check that it is valid to reassign C with B and C' with B', giving us an equally good assignment in which C and B are assigned. Hence, an optimal solution always exists in which C and B are paired, so it is safe to match them together. An alternate, symmetric, solution to this problem is the following: process the cows in increasing order of maxSPF, and for each cow C in sequence, assign C to the minimum SPF bottle compatible with C. The analysis of this approach follows essentially the same reasoning as above. In terms of running time, one can implement either of the two algorithms above in O(n log n) time. One way to do this is the following (in the case of the first algorithm above): We first sort the bottles by SPF rating and the cows by minSPF rating. We then scan the bottles in order and maintain a min-heap on the cows (keyed on maxSPF) with minSPF lower than the SPF of our current bottle. For each bottle B in order, we match it with the minimum cow from the heap (after first removing any cows from the heap having maxSPF less than the SPF of B).

• 我就知道不是网络流 >.< (2423) cuiaoxiang 2008-07-08 18:15:29
• 谢了,我也以为是网络流>_< (2423) Acsaga 2008-07-08 18:24:39
• Re:Analysis (11) zyl072 2008-07-10 10:33:16
• 用网络流AC的人郁闷的飘过。。 (18) zhymaoiing 2009-05-21 14:14:06
  • Re:用网络流AC的人郁闷的飘过。。 (43) 519232826 2012-06-21 20:29:30