[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)))$，可以通过本题。 # 代码示例 ```cpp #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; } ```