Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

## 原装解题报告majia001
at 2006-08-20 12:51:54
on Problem 2976
In Reply To:能说一个吗？ Posted by: nuanran
at 2006-08-19 16:55:50
Drop ---- This problem was intended to be the hardest problem in the set, and indeed, nobody solved it. When choosing to drop tests, there is a trade-off between tests with very low percentage scores and tests with mediocre percentage scores but with a large number of questions. Which one of these is better can depend on the other tests you are keeping. Figuring out how to balance these requirements is the heart of this problem. The first thing you have to realize is that a simple greedy algorithm is not going to be correct. For example, it seems reasonable to drop tests one at a time, always choosing to drop the test that will improve your cumulative average by as much as possible. However, it turns out this is wrong. For example, consider dropping 2 tests from a group of 100/100, 14/50, 14/50, 100/200, and 100/200. The greedy approach would first drop a 14/50 test and then a 100/200 test to get a score of 214/350 = 61%, but the optimal strategy is to drop both 100/200 tests for a score of 128/200 = 64%. If you have done a lot of other programming competitions, you might also think of the dynamic programming approach (see the stones write-up). By tracking the number of questions and the number of tests, you can use this to solve the problem in (number of questions)*(number of tests) time. Unfortunately, the maximum number of questions over all the tests is a trillion, so that is no good either. What do you do then? It turns out that the problem can be solved with a binary search. We ask the following question: "Can you drop k tests to make your cumulative average at least x?". It turns out that fixing x makes the problem substantially easier because this is enough to determine which tests are better than others. If we fix x, we need to choose tests so that (sum a_i) / (sum b_i) >= x <=> sum a_i >= sum (x*b_i) <=> sum (a_i - x*b_i) >= 0. Thus, we compute c_i = a_i - x*b_i for each i. We now need to drop k of those values so that their sum is at least 0. This is a much easier problem! Just sort the c_i's and drop the k smallest values. This reduces everything to a standard binary search problem. For each x, we can test whether we can get an average of at least x, and we need to find the maximum average that can be made. C++ code is shown bleow. double lb = 0, ub = 1; for (i = 0; i < 100; i++) { double x = (lb+ub)/2; for (j = 0; j < tests; j++) scores[j] = num[j] - x*den[j]; sort(scores, scores+tests); double total = 0; for (j = k; j < tests; j++) total += scores[j]; if (total >= 0) lb = x; else ub = x; } cout << int(100*lb + 0.5) << endl; Followed by:- 太强了！
(2848)
**S1**2006-08-20 13:19:06 - 进来看看
(79)
**xtu723**2008-09-18 19:28:08 - 牛X
(2)
**ZaakDov**2009-09-24 20:48:31 - Re:原装解题报告
(9)
**weihaohaoren**2012-01-26 17:18:12
Post your reply here: |

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator