leetcode

commit 0a244a958445151eee968b310939e93843f31af0
parent 5f258ef57fc3afb89a357d5cac2027156a56c034
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 11 May 2024 15:43:42 +0200

Daily Problem

Diffstat:
A
Problems/0857.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/0857.cpp b/Problems/0857.cpp
@@ -0,0 +1,24 @@
+#include <span>
+
+class Solution {
+  public:
+    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
+        static int idx[100001];
+        const int n = size(wage);
+
+        iota(idx, idx + n, 0);
+        sort(idx, idx + n,
+             [&](int a, int b) { return (double)wage[a] / quality[a] < (double)wage[b] / quality[b]; });
+
+        priority_queue<int> pq;
+        double res = DBL_MAX, crnt = 0;
+        for (const int i : std::span(idx, idx + n)) {
+            crnt += quality[i];
+            pq.push(quality[i]);
+            if (size(pq) > k) crnt -= pq.top(), pq.pop();
+            if (size(pq) == k) res = min(res, crnt * wage[i] / quality[i]);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -519,6 +519,7 @@ for solving problems.
 |  0852  |   Medium   | [Peak Index in a Mountain Array](Problems/0852.cpp)                                                |
 |  0853  |   Medium   | [Car Fleet](Problems/0853.cpp)                                                                     |
 |  0856  |   Medium   | [Score of Parentheses](Problems/0856.cpp)                                                          |
+|  0857  |    Hard    | [Minimum Cost to Hire K Workers](Problems/0857.cpp)                                                |
 |  0858  |   Medium   | [Mirror Reflection](Problems/0858.cpp)                                                             |
 |  0859  |    Easy    | [Buddy Strings](Problems/0859.cpp)                                                                 |
 |  0861  |   Medium   | [Score After Flipping Matrix](Problems/0861.cpp)                                                   |