LeetCode weekly-180-4: 1383. Maximum Performance of a Team
$ n人の Employee がいて、それぞれ speed と efficiency が定められている。このうち$ 1以上$ k以下の人数を選び、その集合の$ (\sum E_{s}) * min(E_{e})を最大化せよ。($ E_{s}, E_{e} はある Employee の speed, efficiency)
制約: $ 1 \leq K \leq N \leq 10^5
---
考察:
$ min(E_{e})を固定した場合の最大のケースを考えると、これは$ \sum E_{s}が最大となるケースであることがわかる。
ということは、 efficiency が$ min(E_{e})以上であるもののうち$ E_{s}が大きいものから$ k個取る感じになる。
当然あり得る$ min(E_{e})に対してこれを行うと間に合わないが、$ E_{s}の大きいものを含むようにすることから、近い$ min(E_{e})に対しては集合がほぼ同じになる感がある。$ min(E_{e})の最大値から順に試すとしたらどうなるだろうか?
$ min(E_{e})が最大を取るケースから順に考えると、これは$ E_{e}で降順に並べて先頭$ 1〜$ k個を取る場合となる。これをまず試し最大値を得ておく。
降順に並べてあるから、$ k+1個目以降を集合に入れていくことを考えれば$ min(E_{e})を網羅的に減らせるはず。ただしここで、$ k+1個目の speed が既存の集合の最小の speed 以下であれば取り入れる必要が無いことがわかる。逆にそうでなければ、それを取り入れて最小のものを取り除くことで、集合が「 efficiency が$ min(E_{e})以上のもので speed の総和が過去最大のもの」を保つことができる。これが最大値を超えるかどうかを見ていけば良い。
既存の集合の最小の speed を取得できるようにするためには priority queue を使えば良い。