ABC294 F - Sugar Water 2 (500)
目標の濃度を決め、それ以下の濃度の食塩水がいくつ作れるか二分探索で求めることで答えを求める
目的の濃度を$ p とすると$ \frac{A+C}{B+D} \ge p
$ B,Dは砂糖の量も含むようにしておく
これを$ A,Bと$ C,Dで分かれるようにすると$ C-pD \ge pB-A
よって、目的の$ p以上の濃度の個数は以下で求まる
高橋君の砂糖水全てについてそれぞれ$ pB-Aを求めてソート
青木君の砂糖水それぞれについて以下を行う
$ C-pDを求める
これ以下の値の個数を高橋君の砂糖水から求めた配列から二分探索する
個数が$ k以上であればOK