POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》-码农场
乍看以为贪心或dp能解决，后来发现贪心策略与当前的总体准确率有关，行不通，于是二分解决。
依然需要确定一个贪心策略，每次贪心地去掉那些对正确率贡献小的考试。如何确定某个考试[a_i, b_i]对总体准确率x的贡献呢？a_i / b_i肯定是不行的，不然例子里的[0,1]会首当其冲被刷掉。在当前准确率为x的情况下，这场考试"额外"对的题目数量是a_i – x * b_i，当然这个值有正有负，恰好可以作为"贡献度"的测量。于是利用这个给考试排个降序，后k个刷掉就行了。
之后就是二分搜索了，从0到1之间搜一遍，我下面的注释应该很详细，不啰嗦了。
题目的大数据测试用例可以在http://ai.stanford.edu/~chuongdo/acm/2005/找到，有完整的输入输出可供检验自己的程序。
这题吃了点亏，开始没看清楚题目，给主循环的跳出逻辑写为while (cin >> n >> k && (n && k))，后来看到上面的测试用例里有1 0才恍然大悟，整个人表情变成下面这样：
Read full article from POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》-码农场
No comments:
Post a Comment