[ABC294F] Sugar Water 2
考虑二分答案。
二分出来一个 \(mid\),然后检验浓度 \(\ge mid\) 的糖水数量,如果 \(\ge k\) 说明小了,否则说明大了。
考虑到每个糖水对于 \(mid\),那么它们都需要增加/失去一定数量的糖以达到浓度。
设为 \(e_i\),则 \(e_i=a_i-b_i/(1-mid)*mid\),很好理解,就是对于一定数量的水,你需要再增加/减少多少糖使得浓度为 \(mid\),减号后的就是对于 \(b_i\) 需要的糖。
然后对于 \(c_i,d_i\) 也搞一个,对于每个 \(c_i,d_i\) 的 \(E_i\),都需要满足 \(e_j\ge -E_i\)(因为 \(e_j+E_i\ge0\) 就可以保证浓度超过 \(mid\))。再二分即可。
所以就是一个二分套二分的东西。。。