minimum-cost-to-hire-k-workers

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There are <code>n</code> workers. You are given two integer arrays <code>quality</code> and <code>wage</code> where <code>quality[i]</code> is the quality of the <code>ith</code> worker and <code>wage[i]</code> is the minimum wage expectation for the <code>ith</code> worker.

We want to hire exactly <code>k</code> workers to form a paid group. To hire a group of <code>k</code> workers, we must pay them according to the following rules:

<ol>
	<li>Every worker in the paid group must be paid at least their minimum wage expectation.</li>
	<li>In the group, each worker&#39;s pay must be directly proportional to their quality. This means if a worker&rsquo;s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.</li>
</ol>

Given the integer <code>k</code>, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within <code>10-5</code> of the actual answer will be accepted.

&nbsp;
Example 1:

<pre>
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.
</pre>

Example 2:

<pre>
Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == quality.length == wage.length</code></li>
	<li><code>1 &lt;= k &lt;= n &lt;= 104</code></li>
	<li><code>1 &lt;= quality[i], wage[i] &lt;= 104</code></li>
</ul>

mincostToHireWorkers

Minimum Cost to Hire K Workers

Maximum Subsequence Score

maximum-subsequence-score

最大子序列的分数

Greedy

Array

Sorting

Heap (Priority Queue)

有 <code>n</code>&nbsp;名工人。&nbsp;给定两个数组&nbsp;<code>quality</code>&nbsp;和&nbsp;<code>wage</code>&nbsp;，其中，<code>quality[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;名工人的工作质量，其最低期望工资为&nbsp;<code>wage[i]</code>&nbsp;。

现在我们想雇佣&nbsp;<code>k</code>&nbsp;名工人组成一个&nbsp;工资组。在雇佣&nbsp;一组 <code>k</code>&nbsp;名工人时，我们必须按照下述规则向他们支付工资：

<ol>
	<li>对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。</li>
	<li>工资组中的每名工人至少应当得到他们的最低期望工资。</li>
</ol>

给定整数 <code>k</code> ，返回 组成满足上述条件的付费群体所需的最小金额&nbsp;。与实际答案误差相差在&nbsp;<code>10-5</code>&nbsp;以内的答案将被接受。

&nbsp;

<ol>
</ol>

示例 1：

<pre>
输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。</pre>

示例 2：

<pre>
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。</pre>

&nbsp;

提示：

<ul>
	<li><code>n == quality.length == wage.length</code></li>
	<li><code>1 &lt;= k &lt;= n &lt;= 104</code></li>
	<li><code>1 &lt;= quality[i], wage[i] &lt;= 104</code></li>
</ul>