SRM635Div1Medium
問題
サイズNの数列placeとcutoffが与えられる。全ての要素でとなるために、place内で要素を入れ替える。入れ替えが必要な要素の最小数を求めよ。不可能な場合は-1を返す。
解法
二部マッチングで解こうとすると、となり間に合わない。
貪欲法で解く。
すでにの条件を満たしている集合goodと、満たしていない集合badを作成する。bad内でソートを行い条件を満たすかを値が小さい順に確認していく。満たさない要素を見つけたら、goodから要素を持ってきて満たすようにする。goodから持ってくる要素では、まずを満たす必要がある。この条件を複数の要素が満たす場合は、その中でが最大の要素を選択する。
goodから要素を持ってこれなくなった場合は、条件を満たせないことになるので-1を返す。最後まで処理できた場合は、badの要素数が答えとなる。
計算量
O(N^2 log N)
ソート: O(N log N)