ARC050-B:花束
問題
https://beta.atcoder.jp/contests/arc050/tasks/arc050_b
赤い花が 本、青い花が 本ある。以下の条件を満たすように花束を作る時最大いくつつくれるか?
考え方
最大の花束の数を としよう。1, 2の花束の数をそれぞれ 個作れるとして、「 個の花束を作れるか」という Yes / No 問題を考える。制約条件は
である。上記を満たすような最大の を二分探索で求めれば良い。
public void solve(int testNumber, InputReader in, PrintWriter out) { long R = in.nextLong(), B = in.nextLong(); long x = in.nextLong(), y = in.nextLong(); long l = 0, r = Long.MAX_VALUE/3; while (r - l > 1) { long k = (r+l)/2; if (k <= (R-k)/(x-1) + (B-k)/(y-1)) { l = k; } else { r = k; } } out.println(l); }
ポイント
- 解を仮定して二分探索