射撃王

問題概略
風船がN個H[i]にあり、秒速S[i]で高さが上昇していく。
1秒に一回風船を割れるとして、割った時の最大の高さの最小値を求めよ。

解法
2分法で解きたくなる。
それぞれの風船について、今まで使っていない秒数の内ぎりぎりセーフの秒数を選んでいく貪欲で確認できる。
treesetを使い、今までに使っていない秒数を入れておき、使ったらremove。自分以下の物が無ければアウトという風にやれる。
（解説では風船を時間的余裕順にソートしていて楽でいいなと思った）

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        H = nlah(N, 2);
        S = nlah(N, 2);
        wor = new long[N];
        for (int i = 0; i < N; i++) {
            wor[i] = H[i] + S[i] * (N - 1);
        }
        System.out.println(mgr((long) 1e15, -1));
    }

    public static boolean calc(long v) {
        //貪欲にギリギリセーフを選んでいく。
        boolean[] used = new boolean[N];
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            set.add(i);
        }
        //worはN-1 の結果
        for (int i = 0; i < N; i++) {
            //はみ出ない最高のところ
            long minh = H[i];
            if (v - minh < 0) return false;
            int besi = (int) min((v - minh) / S[i], N - 1);
            Integer sec = set.lower(besi + 1);
            if (sec == null) return false;
            set.remove(sec);
        }
        return true;
    }

    //条件を満たす最大値、あるいは最小値を求める
    static long mgr(long ok, long ng) {
        //int ok = 0; //解が存在する
        //int ng = N; //解が存在しない
        while (Math.abs(ok - ng) > 1) {
            long mid;
            if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
            else mid = ok + (ng - ok) / 2;

            if (calc(mid)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }