Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Analysis

Posted by NASCI at 2008-07-08 17:24:16 on Problem 3614
In Reply To:这题是网络流么? Posted by:zyl072 at 2008-07-08 16:27:50
> 用网络流写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).

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator