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``。 自建示例 -------- 较高最低工资比例决定全组单价: .. code-block:: text 输入:quality = [4,8,2], wage = [20,24,12], k = 2 输出:36.0 解释:选择质量 4 和 2 的工人时,为满足第二人的最低工资,每单位质量至少支付 6;两人的工资为 24 和 12,总额 36。其他两人组合的最低总额都是 60。 只需雇用一名工人: .. code-block:: text 输入:quality = [7,3], wage = [14,12], k = 1 输出:12.0 解释:k 达到允许的最小值 1,此时组内比例条件不会约束其他人。分别单独雇用两人的最低成本是 14 和 12,因此选择第二人即可得到最小总额 12。