P857 - Minimum Cost to Hire K Workers

Problem Abstraction

• hire exactly k workers, find least amount of money
• $pa{y}_i\ge w_i$
• $pa{y}_i/q_i=pa{y}_j/q_i$

Conclusions

Theorem 1: 在最优发工资的方案下, 至少有一名工人, 发给他的工资恰好等于他的最低期望工资.

Theorem 2: 定义 $r_i=\frac{w_i}{q_i}$. 若以某人的 $r_i$ 为基准发工资, 那么对于不超过 $r_i$ 的工人, 发给他们的工资是不低于其最低预期工资的, 因此, 这些工人是可以随意选择的.

Code

/// runs in O(nlogn)/O(n)
pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
    use std::collections::BinaryHeap;

    let n = quality.len();
    let k = k as usize;
    let mut id: Vec<_> = (0..n).collect();

    id.sort_unstable_by(|&i, &j| (wage[i] * quality[j]).cmp(&(wage[j] * quality[i])));

    let mut h = BinaryHeap::new();
    let mut sum_q = 0;
    for i in 0..k {
        h.push(quality[id[i]]);
        sum_q += quality[id[i]];
    }

    let mut ans = sum_q as f64 * wage[id[k - 1]] as f64 / quality[id[k - 1]] as f64;

    for i in k..n {
        let q = quality[id[i]];
        if q < *h.peek().unwrap() {
            sum_q -= h.pop().unwrap() - q;
            h.push(q);
            ans = ans.min(sum_q as f64 * wage[id[i]] as f64 / q as f64);
        }
    }

    ans
}