【练习】小咪买东西

小咪买东西

https://ac.nowcoder.com/acm/problem/14662

题目

题目描述：

小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办。

而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。

输入描述：
多组数据。
第一行一个整数T，为数据组数。
接下来有T组数据。
对于每组数据，第一行两个正整数n，k，如题。

接下来n行，每行有两个正整数ci，vi。分别为手办的花费和它对于小咪的价值。

输出描述：
对于每组数据，输出一个数，即能得到的总价值/总花费的最大值。精确至整数。

解析

1）知识点

这道题就是一道简单的01分数规划，再运用二分。

2）看题目

这道题要求单位价值（题目中的总价值/总花费），我们假设单位价值为x，我们就可以知道，x = Σv / Σc。

3）算法分析

我们已经知道了这道题是要二分，那么我们就对单位价值进二分，也就是我们要求的答案。
由上面我们设立的公式：变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。
如果我们选取的v和c使这个式子>0的话，说明至少还有一组v和c可以使得x更大：Σv - Σc * x > 0。这就是：x < Σv / Σc（算出了答案可以比二分猜测的x大）。
所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的k个。进行Σv - Σc * 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] = v[i] - x * c[i];
    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）打代码

所以我们先把c，v输入了。
然后二分猜测答案。
不断缩小范围，按照上面讲的二分判断进行判断。
下面全代码~

AC代码

#include <iostream>
#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 = 1e4 + 7;
int n, k;
int c[MAX], v[MAX];
double w[MAX];
//全局变量区

bool judge(double x) {
    for (int i = 1; i <= n; i++)
        w[i] = v[i] - x * c[i];
    sort(w + 1, w + 1 + n, greater<double>());
    double sm = 0;
    for (int i = 1; i <= k; i++)
        sm += w[i];
    return sm > 0;
}
//函数预定义区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> c[i] >> v[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 << (int)r << endl;
    }
    return 0;
}
//函数区

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏