AOJ 2374 RabbitLunch
解法
O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします
ヒントはフロー(僕はこれをsnukeに教えてもらった)
かなり面白いので、すぐに見ないほうがいいかも。
見たい人は下までスクロール
与えられた条件を二部グラフのフローの形にしてみると、
source-人参(流量は人参の個数)
人参-キウイ(m*n の辺を張る。流量はすべて1)
キウイ-sink(流量はキウイの個数)
の辺を張る。
求める値はこのグラフでの最大フロー
これは最小カットに等しい。
source-人参の辺からK本、キウイ-sinkの辺からL本カットに入れると、
人参-キウイの(M-K)*(N-L)本を切ればよい。
よって、source-人参の辺・キウイ-sinkの辺 を切るときは、流量の小さいものから切っていけばいい。
source-人参の辺の切る数をiとして0...Nまで動かす。
人参-キウイ、キウイ-sink での最小カットは、
X軸にキウイ-sinkの切る辺の数を取ると、
この2つのグラフを合わせたような感じになる。
キウイ-sinkのグラフは、切る辺は小さい順に並んでいるので、下に凸
人参-キウイのグラフはそもそも直線
となり、和を取ったグラフも下に凸
なので、局所解が大域解になってる
ところで、iを1つ大きくした時、キウイ-sinkのグラフは変わらず、
人参-キウイのグラフは傾きが小さくなる。
このとき、キウイ-sinkの切る数の解は少なくなる方向にのみ動くことがわかる。
よって、iを増やしながら、しゃくとり法をすればいいことが分かる。
ソートをバケツソートで行うと、すべてO(N)
