准确率:n场考试中分别答对a_i题,总题数分别为b_i,允许去掉k场考试,求能达到的最高准确率。
3.1不光是查找值!“二分搜索”
最大化平均值
乍看以为贪心或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才恍然大悟,整个人表情变成下面这样:
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; #define MAX_N 1000 int n, k; double x; // 搜索过程中的正确率 struct Test { int a, b; bool operator < (const Test& other) const { return a - x * b > other.a - x * other.b; // 按照对准确率的贡献从大到小排序 } }; Test test[MAX_N]; // 判断是否能够获得大于mid的准确率 bool C(double mid) { x = mid; sort(test, test + n); double total_a = 0, total_b = 0; for (int i = 0; i < n - k; ++i) // 去掉后k个数计算准确率 { total_a += test[i].a; total_b += test[i].b; } return total_a / total_b > mid; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (cin >> n >> k && (n || k)) { for (int i = 0; i < n; ++i) { cin >> test[i].a; } for (int i = 0; i < n; ++i) { cin >> test[i].b; } double lb = 0; double ub = 1; while (abs(ub - lb) > 1e-4) { double mid = (lb + ub) / 2; if (C(mid)) { lb = mid; // 行,说明mid太小 } else { ub = mid; // 不行,说明mid太大 } } cout << fixed << setprecision(0) << lb * 100 << endl; } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12821055 | hankcs | 2976 | Accepted | 264K | 157MS | C++ | 1479B | 2014-04-30 00:59:27 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》