ABC294F 题解

· · 个人记录

前置说明

为了更直观，在题解中先把浓度计算中的 100 去掉，最后求出答案，乘上 100 就行了。

即有 a 单位糖，b 单位水，那么浓度暂且设为 \frac{a}{a+b}。

另外简单推式子得到，浓度为 \frac{a}{a+b} 的溶液，加上 \frac{(a+b)c - a}{1-c} 份糖之后，浓度变为 c。

题解

考虑二分第 K 大，设二分到 c。
考虑怎么求出有多少种配对方式浓度大于 c。
然后计算青木君每个瓶子有多少糖是多余的，将其放入数组 more，显然 more_i = -\frac{(a+b)c - a}{1-c}。
然后对 more 排序。
然后枚举高桥君的每个瓶子，看与多少个青木君的瓶子放在一起浓度大于 c，这显然二分一下就行了。

由于我手懒不需要提交到洛谷，就不说细节了。

代码见Atcoder提交记录