2018年东北农业大学春季校赛 I-wyh的物品
链接：https://www.nowcoder.com/acm/contest/93/I
来源：牛客网
题目描述
wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值
输出描述:
对于每组测试数据，输出对应答案，结果保留两位小数
示例1
输入
1
3 2
2 2
5 3
2 1
输出
0.75
说明
对于样例来说，我们选择第一个物品和第三个物品，达到最优目的
思路
咋眼一看（其实看了也很久），以为是背包（一直往背包方向上靠）。
但其实这是求一个最大化的平均值（使用二分法）。
这可能有点难理解。我们不妨把（目标要求的）单位价值设为x，差值为y。
y = 重量 * x - 价值
为了保证x最大，我们取y值前k大的（重量，价值）对。
对于每组（重量，价值）对，逐一计算出y值，然后递增排列，取前k个计算得出（总质量，总价值）。
使用二分寻找出目标x，对应差值y应接近于0：
y = 总重量 * x - 总价值 （y → 0）
使用二分缩小x取值范围，直到满足规定的最小精度。
AC代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct things {
double a; // 重量
double b; // 价值
};
double low,mid,high;
bool cmp(things fir, things sec) {
return mid * fir.a - fir.b < mid * sec.a - sec.b;
}
int main() {
int T;
cin >> T;
while(T--) {
int n,k;
cin >> n >> k;
vector<things> vec;
for(int i=0; i<n; i++) {
double a,b;
cin >> a >> b;
things th;
th.a = a;
th.b = b;
vec.push_back(th);
}
double value, weight, ans;
double res; // 差值
low = 0, high = 1000,ans = 0;
while(high-low > 1e-6) {
mid = (low + high) / 2.0;
sort(vec.begin(), vec.end(), cmp);
value = weight = 0;
for(int i = 0; i < k; i++) {
things tmp = vec.at(i);
value += tmp.b;
weight += tmp.a;
}
ans = value / weight;
res = mid * weight - value;
if(res < 0)
low = mid;
else
high = mid;
}
//cout << mid << endl;
cout << fixed << setprecision(2) << ans << endl;
}
return 0;
}
