No.046 C

一見するとマッチング問題に見えるが, 辺の数が最大で $NM$ になるのでこの方法では解けない.

ここで大事なのはお互いに相手の年収しか見ていない(笑)ということである.

まずは男女をまとめて女性の希望額, 男性の年収の順にソートする. ただし, 女性の希望額と男性の年収が同等であれば女性の方が前に来るようにする. このようにすることで, ある男性はそれより前の女性の希望を満たすことになる.

そして, ソートした男女列を前から次のように処理する.

• 女性ならばペア待ちの列に入れる.
• 男性ならばペア待ちの列から女性の年収が自分の希望額より多く, かつその中で最も年収の低い相手を選んで取り出す.

ここで, ペア待ち列を女性の年収順を基準にした赤黒木で管理することで, 男性がペア待ち列から女性を選ぶ作業を $O(\log(N+M))$ で行えるようになる.

これを繰り返し, 男性が選んだ女性の数が最大ペア数である.