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

POJ 3111 K Best

卖宝救夫：Demy要卖珠宝，n件分别价值v_i 重 w_i，她希望保留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//////////////////////////////////

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

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