POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》

POJ 2976 Dropping tests

准确率：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//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2976 Dropping tests 题解 《挑战程序设计竞赛》