题目

题目描述:
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)算法分析

  1. 我们已经知道了这道题是要二分,那么我们就对单位价值进二分,也就是我们要求的答案。
  2. 由上面我们设立的公式:变式可以得到 Σb - Σa * x = 0。我们在二分猜测答案的时候就以这个为基准(为什么呢?看下面)。
  3. 如果我们选取的b和a使这个式子>0的话,说明至少还有一组b和a可以使得x更大:Σb - Σa * x > 0。这就是:x < Σb / Σa(算出了答案可以比二分猜测的x大)。
  4. 所以我们就可以依照这个式子得到每个物品的权值,然后进行排序,选出最大的k个。进行Σb - Σa * x > 0的判断

4)算法操作

  1. 这里要进行二分,首先按模板上二分:
    for (int i = 1; i <= 100; i++){ 
        double mid = (l + r) / 2;
        if (judge(mid)) l = mid;
        else r = mid;
    }
    //这里用循环100次保证精度很高,不用<eps保证不会死循环
  2. 然后就是二分判断怎么写了。
  3. 按上面的说法,就是把Σ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)打代码

  1. 所以我们先把a,b输入了。
  2. 然后二分猜测答案。
  3. 不断缩小范围,按照上面讲的二分判断进行判断。
  4. 下面全代码~


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;
}
//函数区