leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0857.cpp (722B)

      1 #include <span>
      2 
      3 class Solution {
      4   public:
      5     double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
      6         static int idx[100001];
      7         const int n = size(wage);
      8 
      9         iota(idx, idx + n, 0);
     10         sort(idx, idx + n,
     11              [&](int a, int b) { return (double)wage[a] / quality[a] < (double)wage[b] / quality[b]; });
     12 
     13         priority_queue<int> pq;
     14         double res = DBL_MAX, crnt = 0;
     15         for (const int i : std::span(idx, idx + n)) {
     16             crnt += quality[i];
     17             pq.push(quality[i]);
     18             if (size(pq) > k) crnt -= pq.top(), pq.pop();
     19             if (size(pq) == k) res = min(res, crnt * wage[i] / quality[i]);
     20         }
     21 
     22         return res;
     23     }
     24 };