poj 3111 K Best 最大化平均值

缘起

日常浪费生命 poj 3111 K Best

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
丈夫资金紧张，妻子不得不售卖自己的珠宝来缓解. 妻子有n件珠宝,每件的重量是wi克拉,价值是vi
但是妻子希望为自己保留k件珠宝，并且这k件珠宝的平均每克拉价值最大. 输出妻子的选择的k件珠宝
（如果有多种最优，任意输出一种都行）

【输入】
n,k 然后是n行，每行两个整数v和w
1 ≤ k ≤ n ≤ 100 000
0 ≤ vi ≤ 10^6, 1 ≤ wi ≤ 10^6, both the sum of all vi and the sum of all wi do not 
exceed 10^7

【输出】
妻子的选择

【样例输入】
3 2
2 2
3 5
1 2

【样例输出】
1 3

【限制】
8s

【是否接受Special Judge】
是

本题其实比较容易想到的是贪心. 就是直接按照性价比从高到低排序, 然后取前k就行了. 但是题目出的比较良心. 给出的样例输入就指明了此路不通.（不然话说回来——会需要8s么?）

本题可以使用二分答案. 判断条件为平均值可否到达x以上? 假设我们选择的是前k件物品（注意，仅仅是假设哈~）

则

(v1+…+vk)/(w1+…+wk)>=x, 等价于

\Sigma(vi-x*wi) 求和>=0

所以对于枚举的x,只需求出v-x*w的最大的k项之和即可.看看是不是>=0.

本题如果知道了简单贪心是错误的，则想到二分答案并不困难. 本题另一个考察点就是精度的控制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const double eps = 1e-8;

int n,k;
struct Goods
{
	int v,w,i; // i是物品原本的索引
	double x;
	bool operator<(Goods o)
	{
		return x>o.x; //按照x降序排序
	}
}goods[100005];

bool ck(double x)
{
	for (int i = 0; i<n;i++)
	{
		goods[i].x = goods[i].v-x*goods[i].w;
	}
	sort(goods, goods+n);
	double tot = 0;
	for (int i=0; i<k;i++)
	{
		tot+=goods[i].x;
		if (tot+eps<0) // 如果tot<0的话, 则已经不可能了
		{
			return false;
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&k);
	double _max = 0;
	for (int i = 0; i<n;i++)
	{
		scanf("%d%d", &goods[i].v, &goods[i].w);
		goods[i].i = i+1;
		if (1.0*goods[i].v/goods[i].w>_max+eps) // 如果真的>_max的话
		{
			_max = 1.0*goods[i].v/goods[i].w;
		}
	}
	double lo = 0, hi = _max, mid, ans;
	while(hi>lo+eps) // 如果hi 真的还>lo的话
	{
		mid = (lo+hi)/2;
		if (ck(mid))
		{
			ans = mid;
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	} // 最终将得到一种答案
	for (int i = 0; i<k;i++)
	{
		if (i)
		{
			putchar(' ');
		}
		printf("%d", goods[i].i);
	}
	return 0;
}

ac情况（水过水过~ 跑了快2s了!）

Status Accepted
Time 1735ms
Memory 2460kB
Length 1165
Lang C++
Submitted 2019-09-01 16:25:45
Shared
RemoteRunId 20823567