最大化平均值
有n个物品的重量和价值分别wi 和 vi。从中选出 k 个物品使得 单位重量 的价值最大。 限制条件：
<= k <= n <= ^
<= w_i <= v_i <= ^6 输入：
n = 3
k = 2
{W, V} = {(2,2), (5,3), (2,1)} 输出：
0.75 （如果选0号和2号，平均价格是 (2 + 1) / (2 + 2) = 0.75）
题解：
一般先想到的肯定是：把物品按照 单位价值 进行排序，然后从大到小贪心地进行选取。但是这个方法对应输入得到的 是 5/7=0.714。不可行。
转换成二分搜索的问题，由之前的博客中，这种题目关键就是 编写二分的条件C(x)。
- C(x) = 可以选择使得 单位重量的价格 不小于 x
假设 n组数据，那他们 单位重量的价格是：
- sum(vi) / sum(wi)
因此就变成了：
- sum(vi) / sum(wi) >= x
转换为：
- sum(vi - x * wi) >= 0
对 (vi - x * wi )的值进行排序贪心地进行选取。因此：
- C(x) = ((vi - x*wi) 从大到小排列中的前 k 个的和不小于0)，即说明改 x 可以达到 k 个物品的 单位重量的价值
- 然后，就是用 二分搜索，来进行得到 最大满足这一条件的 x
#include <iostream>
#include <functional>
#include <algorithm>
using namespace std; /*
3
2
2 2 5 3 2 1
*/
const int maxn = + ;
int n, k;
int w[maxn], v[maxn];
double ave[maxn]; //判断是否满足条件
bool C(double x)
{
for (int i = ; i < n; i++)
{
ave[i] = v[i] - x * w[i];
}
//如果要自定义排序，里面别写成int了.....答案会出错...
sort(ave, ave + n, greater<double>()); // for (int i = 0; i < n; i++) {
// cout << ave[i] << " ";
// }
// cout << endl; //按从大到小取k个数求和
double sum = ;
for (int i = ; i < k; i++) {
sum += ave[i];
} //观察是否 可以取到 x为平均值
return sum >= ;
} void solve()
{
int INF = ;
cin >> n >> k;
for (int i = ; i < n; i++)
{
cin >> w[i] >> v[i];
INF += v[i];
} double lh = , rh = INF, mid;
for (int i = ; i < ; i++)
{
mid = (lh + rh) / 2.0;
if (C(mid)) {
lh = mid;
}
else {
rh = mid;
}
}
printf("%.2f\n", lh);
} int main()
{
solve();
return ;
}
习题：POJ 2976 Dropping tests
来源：http://poj.org/problem?id=2976
题意：题目就是说，n个题目，你可以少做k个题目, 然后 n个题目分别为你得到的分数 ai, 和题目的分数 bi , 有个公式是：
， 要求就是：均值最大为多少，需要四舍五入。输入多组数据，n, k同时为0时，终止输入。和上面的例题属于一模一样的题目, 用二分解决最大化平均值的问题。
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = + ;
typedef long long LL;
int n, k;
LL a[maxn], b[maxn];
double INF;
double ave[maxn]; bool C(double x)
{
for (int i = ; i < n; i++)
{
ave[i] = a[i] - x * b[i];
} //降序
sort(ave, ave + n, greater<double>()); double sum = ;
for (int i = ; i < n - k; i++)
{
sum += ave[i];
} return sum >= ;
} void solve()
{
double lh = , rh = INF, mid;
for (int i = ; i < ; i++)
{
mid = (lh + rh) / ;
if (C(mid))
{
lh = mid;
}
else
{
rh = mid;
}
}
//和下面那种都可以
printf("%.f\n", lh * );
// cout << fixed << setprecision(0) << lh * 100 << endl;
} int main()
{
while (cin >> n >> k && (n || k))
{
for (int i = ; i < n; i++) {
cin >> a[i];
INF += a[i];
}
for (int i = ; i < n; i++) {
cin >> b[i];
}
solve();
}
return ;
}