[ABC294F] Sugar Water 2题解

· · 题解

题意简述

高桥君有 n 瓶糖水，编号为 1 到 n，其中第 i 瓶糖水中含有 a_i 克糖和 b_i 克水。青木君有 m 瓶糖水，编号为 1 到 m，其中第 i 瓶糖水中含有 c_i 克糖和 d_i 克水。

现在高桥君随意选出一瓶水，青木君也随意选出一瓶水，混合在一起，这样总共有 n \times m 种不同的混合方式。所有混合方式中，按照浓度从高到低排序，问排第 k 的混合方式的浓度是多少。浓度计算方式为，如果一瓶水中有 x 克糖，有 y 克水，浓度为 \frac{100 \times x}{x+y}。

解题思路

本题数据范围 n,m \le 5 \times 10^4，总的方案太多了，如果全枚举出来，再排序一遍，复杂度是 n \times m \log(n \times m) ，这样肯定要超时。

题目中问我们浓度第 k 大的方案的浓度，不妨设为 cc，那么我们可以二分这个浓度 cc，然后计算所有混合液当中，浓度比 cc 大的方案数 cnt。如果发现 cnt \lt k，说明我们选择的 cc 是可行的，继续去小的那边二分。否则说明我们选择的 cc 太小了，它肯定不是目标浓度，就去大的那边二分。

下面问题就是，当给定浓度的时候，如果求出浓度比它大的方案数呢？

首先对于青木君的 m 瓶糖水，假设每瓶水中糖有 x 克，水有 y 克。我们假设要把它调整为浓度为 cc 的，则在水不变的情况下，糖需要 cc \times y / (1 - cc) 克，而现有的糖为 x 克，那么这瓶水当中多余的糖为 x - cc \times y / (1 - cc) 克。我们可以算出每一瓶里面多余的糖，然后按照这个数字对青木君的 m 瓶糖水排序。请注意，这里多余的糖可能为负数，表示的是缺少多少糖。负数也没关系的，正常放到数组里排序。

接下来枚举高桥君的 n 瓶糖水，对于当前这一瓶，还是用一样的方式，我们可以算出这一瓶糖水中，多余的糖是多少，然后取个负，变成缺多少糖，记为 less。则我们可以到刚才排好序的数组里面二分查找，找到有多少个数字是大于 less 的，那么这些都可以和当前这瓶组合出浓度超过 cc 的混合液。

这样排序复杂度 O(m\log(m))，枚举和二分查找的复杂度 O(n\log(m))，外面再套 100 层二分浓度 cc 就行了。题目中要求精度是 10^{-9}，我们二分 100 次，精度是 2^{-100}，肯定够了。这样总的复杂度是 O(100 \times ((m+n)\log(m)))，可以通过本题。

代码示例

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;

ll n, m, k;
double a[MAXN], b[MAXN], c[MAXN], d[MAXN], more[MAXN];

//计算浓度大于mid的方案数
ll check(double cc) {
    //浓度是cc,对于m个瓶子，水是y，则糖需要cc * y / (1 - cc)
    //多余的糖是x - cc * y / (1 - cc)，把每个瓶子中多余的糖放到more数组里
    for (int i = 0; i < m; ++i) {
        more[i] = c[i] - cc * d[i] / (1 - cc);
    }
    //按照多余的糖排序
    sort(more, more + m);
    ll cnt = 0;
    //遍历n个瓶子，对于每个瓶子，计算它缺少的糖
    for (int i = 0; i < n; ++i) {
        double less = -(a[i] - cc * b[i] / (1 - cc));
        //二分查找，找到所有多余的糖比less多的个数
        ll t = more + m - upper_bound(more, more + m, less);
        cnt += t;
    }
    return cnt;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> c[i] >> d[i];
    }
    //二分排名第k的浓度
    double low = 0, high = 1, mid;
    for (int i = 0; i < 100; ++i) {
        mid = (low + high) / 2;
        if (check(mid) < k) {
            high = mid;
        } else {
            low = mid;
        }
    }
    printf("%.15lf\n", high*100);
    return 0;
}