0857. Minimum Cost to Hire K Workers

题目信息

题号:

0857

难度:

Hard

主题:

工人选择、比例工资、最小成本

原题:

LeetCode 0857

重点:

必须恰好雇用 k 人;组内每人的实际工资与质量成同一比例,同时不得低于各自最低期望工资

题目重述

有 n 名工人,第 i 人的工作质量为 quality[i],最低期望工资为 wage[i]。需要恰好选择 k 名工人并确定他们的实际工资,且同时满足:

  • 每名被雇工人的实际工资不少于其 wage[i];

  • 在所选组内,任意两人的实际工资之比必须等于其质量之比,也就是所有人使用同一个“每单位质量工资”比例。

请返回满足条件时支付给这 k 名工人的最小工资总额。答案与真实值的误差在 10^-5 以内即可接受。

n == quality.length == wage.length,1 <= k <= n <= 10^4,1 <= quality[i], wage[i] <= 10^4。

自建示例

较高最低工资比例决定全组单价:

输入:quality = [4,8,2], wage = [20,24,12], k = 2
输出:36.0
解释:选择质量 4 和 2 的工人时,为满足第二人的最低工资,每单位质量至少支付 6;两人的工资为 24 和 12,总额 36。其他两人组合的最低总额都是 60。

只需雇用一名工人:

输入:quality = [7,3], wage = [14,12], k = 1
输出:12.0
解释:k 达到允许的最小值 1,此时组内比例条件不会约束其他人。分别单独雇用两人的最低成本是 14 和 12,因此选择第二人即可得到最小总额 12。