サーバはリソースの昇順にソートしておく.

\(k_1, k_2\) を決めたとき, 1番目のサービスは \(p_1 = \lceil x_1/k_1 \rceil\) 以上のリソースを持つサーバにデプロイすることができる. 2番目のサービスは \(p_2 = \lceil x_2/k_2 \rceil\) 以上のリソースを持つサーバにデプロイすることができる.

ここで \(p_1 \leq p_2\) の場合を考える. \(p_1\) より小さいリソースを持つサーバは使うことがないので考えない. このとき, 最初の \(k_1\) 個のサーバに1番目のサービスを割り当て, 2番目のサービスは大きい方から \(k_2\) 個のサーバに割り当てるのが最適となる.

このとき \(k_2\) はできるだけ小さい方がよく, その \(k_2\) の最小値は後ろから計算していけば \(O(N)\) で求めることができる.

あとは \(k_1\) を動かして, リソースが \(p_1\) 以上のサーバの数が \(k_1+k_2\) 以上になるような \(k_1\) を求めればいい. リソースが \(p_1\) 以上のサーバは二分探索で求めることができる.

\(p_1 \gt p_2\) の場合も同様である.