放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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//////////////////////////////////
12821055 hankcs 2976 Accepted 264K 157MS C++ 1479B 2014-04-30 00:59:27

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机