leetcode

0 #include <span>

1

2 class Solution {

3 public:

4 double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {

5 static int idx[100001];

6 const int n = size(wage);

7

8 iota(idx, idx + n, 0);

9 sort(idx, idx + n,

10 [&](int a, int b) { return (double)wage[a] / quality[a] < (double)wage[b] / quality[b]; });

11

12 priority_queue<int> pq;

13 double res = DBL_MAX, crnt = 0;

14 for (const int i : std::span(idx, idx + n)) {

15 crnt += quality[i];

16 pq.push(quality[i]);

17 if (size(pq) > k) crnt -= pq.top(), pq.pop();

18 if (size(pq) == k) res = min(res, crnt * wage[i] / quality[i]);

19 }

20

21 return res;

22 }

23 };