【练习】wyh的物品
wyh的物品
https://ac.nowcoder.com/acm/problem/15446
题目
题目描述： wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个。
问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）
输入描述：
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值
输出描述：
对于每组测试数据，输出对应答案，结果保留两位小数
解析
1）知识点
- 这道题就是一道经典的01分数规划题目，然后二分答案，我是没看出来的。
2）看题目
- 这道题要求单位价值，我们假设单位价值为x，我们就可以知道，x = Σb / Σa。
3）算法分析
- 我们已经知道了这道题是要二分，那么我们就对单位价值进二分，也就是我们要求的答案。
- 由上面我们设立的公式：变式可以得到 Σb - Σa * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。
- 如果我们选取的b和a使这个式子>0的话，说明至少还有一组b和a可以使得x更大：Σb - Σa * x > 0。这就是：x < Σb / Σa（算出了答案可以比二分猜测的x大）。
- 所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的k个。进行Σb - Σa * x > 0的判断。
4）算法操作
- 这里要进行二分，首先按模板上二分：
for (int i = 1; i <= 100; i++){ double mid = (l + r) / 2; if (judge(mid)) l = mid; else r = mid; } //这里用循环100次保证精度很高，不用<eps保证不会死循环 - 然后就是二分判断怎么写了。
- 按上面的说法，就是把Σb - Σa * x作为权值，从大到小排序，并进行k个统计判断就好了：
bool judge(double x) { for (int i = 1; i <= n; i++) w[i] = b[i] - a[i] * x; sort(w + 1, w + 1 + n, greater<double>()); double sm = 0; for (int i = 1; i <= k; i++) sm += w[i]; return sm > 0; } //为了方便我们逆序排序
5）打代码
- 所以我们先把a，b输入了。
- 然后二分猜测答案。
- 不断缩小范围，按照上面讲的二分判断进行判断。
- 下面全代码~
AC代码
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 7;
int n, k;
int a[MAX], b[MAX];
double w[MAX];
//全局变量区
bool judge(double mid);
//函数预定义区
int main() {
IOS;
int T; cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
double l = 0, r = INF;
for (int i = 1; i <= 100; i++){
double mid = (l + r) / 2;
if (judge(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(2) << l << endl;
}
return 0;
}
bool judge(double x) {
for (int i = 1; i <= n; i++)
w[i] = b[i] - a[i] * x;
sort(w + 1, w + 1 + n, greater<double>());
double sm = 0;
for (int i = 1; i <= k; i++)
sm += w[i];
return sm > 0;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
投递零跑科技等公司10个岗位 >
