放牧代码和思想
专注自然语言处理、机器学习算法

POJ 3111 K Best 题解 《挑战程序设计竞赛》

目录

POJ 3111 K Best

卖宝救夫:Demy要卖珠宝,n件分别价值vi 重 wi,她希望保留k件使得

最大。

3.1不光是查找值!“二分搜索”

最大化平均值

晚上A一题睡的香,这题跟POJ 2976 Dropping tests一个原理,注意结束条件的选取,2的50次方已经是相当大的数了,完全可以覆盖解空间。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
#define MAX_N 100000 + 16
int n, k;
double s;
struct Jewel
{
	int v, w;
	int id;
	bool operator < (const Jewel& other) const
	{
		return v - s * w > other.v - s * other.w;
	}
};
Jewel jewel[MAX_N];
int ids[MAX_N];

bool C(double mid)
{
	s = mid;
	sort(jewel, jewel + n);
	double total_v = 0, total_w = 0;
	for (int i = 0; i < k; ++i)                    // 前k个数计算s
	{
		total_v += jewel[i].v;
		total_w += jewel[i].w;
	}

	return total_v / total_w  > mid;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> n >> k;
	double max_s = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> jewel[i].v >> jewel[i].w;
		jewel[i].id = i + 1;
		max_s = max(max_s, (double)jewel[i].v / jewel[i].w);
	}

	double lb = 0; double ub = max_s;
	for (int i = 0; i < 50; ++i)
	{
		double mid = (lb + ub) / 2;
		if (C(mid))
		{
			lb = mid; // 行,说明mid太小
		}
		else
		{
			ub = mid; // 不行,说明mid太大
		}
	}
	for (int i = 0; i < k; ++i)
	{
		ids[i] = jewel[i].id;
	}
	sort(ids, ids + k);
	copy(ids, ids + k, ostream_iterator<int>(cout, " "));
	
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

12824357 hankcs 3111 Accepted 1816K 5797MS C++ 1554B 2014-04-30 23:41:52

我认为这五秒钟是IO的错,不是算法的问题

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

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    楼主,这道题的精度要求有多高啊!我WA了好多次

    qingxi曾4年前 (2015-03-25)回复

我的开源项目

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