857. Minimum Cost to Hire K Workers の解き方メモ

品質あたりに払う給料をコスパ係数と定義します。たとえば、品質20、給料50の労働者のコスパ係数は2.5です。そして、コスパ係数が高いことを「コスパが良い」、その逆を「コスパが悪い」と呼ぶことにします。

Aさんを基準にグループを構成することを考えると、まずはAさんよりコスパの悪いK-1人を選ぶ必要があります。たとえば、Aさん=品質20、給与50、コスパ係数2.5だとします。このとき、Aさんよりコスパの良いXさん=品質5、給与25、コスパ係数5を選ぶと、Xさんに払う給与は20となり、最低給与25を下回ってしまいます。

ここで、Aさんよりコスパの悪いBさんとCさんを選んだとすると、このグループに払う給与は

  Aさんのコスパ係数 * Aさんの品質
+ Aさんのコスパ係数 * Bさんの品質
+ Aさんのコスパ係数 * Cさんの品質

これを整理すると

Aさんのコスパ係数 * (Aさんの品質 + Bさんの品質 + Cさんの品質)

グループに払う給料が最小になる可能性があるのは、Aさんの品質 + Bさんの品質 + Cさんの品質 が最小になるケースです。つまり、Aさんを基準にしたとき、Aさんよりコスパが悪い労働者のうち、品質が低いK-1人を選択すればよいとわかります。

あとはこれを実装します。「Aさんよりコスパが悪い労働者のうち、品質が低いK-1人」については優先度付きキューなどで管理すればよいです。

use std::collections::BinaryHeap;

impl Solution {
    pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
        let mut cost_perfomaces = (0..quality.len())
            .map(|i| (wage[i] as f64 / quality[i] as f64, i))
            .collect::<Vec<_>>();
        cost_perfomaces.sort_by(|(cost_pefomance1, i1), (cost_pefomance2, i2)| {
            cost_pefomance1.partial_cmp(cost_pefomance2).unwrap()
        });

        let mut heap = BinaryHeap::new();
        let mut quality_sum = 0;
        let mut best = f64::MAX;
        for (cost_perfomance, i) in cost_perfomaces {
            if heap.len() == k as usize - 1 {
                best = best.min(cost_perfomance * (quality[i] as f64 + quality_sum as f64));
                heap.push(quality[i]);
                quality_sum += quality[i];
                quality_sum -= heap.pop().unwrap();
            } else {
                heap.push(quality[i]);
                quality_sum += quality[i];
            }
        }

        best
    }
}