Quiz
https://codeforces.com/contest/1159/problem/C
Submission
https://codeforces.com/contest/1159/submission/54040877
問題の意味
A
— こるとん (@kyort0n) 2019年5月12日
男がn人 女がm人います
各男が各女にそれぞれキャンディをいくつかずつ渡します
男iについて、(1人に渡したキャンディの個数の最小値)=a[i]が成立します
女iについて、(1人から受け取ったキャンディの個数の最大値)=b[i]が成立します
総譲与キャンディ数の最小値を求めてください。
解法
- 男性の条件を満たすためにまずbiで配る
- biと一致する女性は条件が満たされたので取り除く
- まだ配られていない女性だけ残る
- 女性の条件を満たすために男性側の配りを変更して合わせていく
- 変更時、男性側のbi条件を崩してはいけないので、各男性の変更可能数はM-1
- biが大きい男性の配りを変更した方が得なので、biが大きい男性から使っていく
学び
- まず片方側の条件を満たしてしまい、そこから調整する
