P1570 KC 喝咖啡（小数二分）

• P1570 KC 喝咖啡

题意：给定调料种数 \(n\) 和能加入的调料数 \(m\)，以及每种调料的美味度 \(v_i\)，消耗的时间 \(c_i\)。

请选择单位时间的美味度最大的咖啡。

分析：\(t=\frac{\sum{v_i}}{\sum{c_i}}\) --- 取最大值，二分答案找右边界。

但是如何确定元素合法？
选择的最优的前 \(m\) 种配料，如果合法，那么继续取右边界。

\(t=\frac{\sum{v_i}}{\sum{c_i}}\) 可以进行变形：\(\sum{v_i}-t*\sum{c_i}=0\)。

所以想要 \(t\) 最大，那么公式整体需要尽可能取大---即配料最优。
此时选择最优的前 \(m\) 种配料即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, v[N], c[N];
double a[N];
// 检查答案为x 时是否满足 ∑v - x * ∑c >=0.
bool chk(double x) {
    for (int i = 1; i <= n; i++)
        a[i] = v[i] - x * c[i];
    sort(a + 1, a + 1 + n, greater<double>());// 降序排序
    double s = 0;
    for (int i = 1; i <= m; i++) s += a[i];
    return s >= 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);

    double l = 0, r = 1000;
    while (r - l > 1e-6) {
        double mid = (l + r) / 2.0;
        if (chk(mid)) l = mid;
        else r = mid;
    }
    printf("%.3lf\n", l);
    return 0;
}