<p>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>i<sup>th</sup></code> worker and <code>wage[i]</code> is the minimum wage expectation for the <code>i<sup>th</sup></code> worker.</p>

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

<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>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class IterPair
{
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = tuple<int, int>;
    using difference_type = int;
    using pointer = tuple<int, int>*;
    using reference = tuple<int&, int&>;
    
    vector<int>* nums1;
    vector<int>* nums2;
    int idx;

    IterPair(vector<int>& nums1, vector<int>& nums2, int idx = 0) : nums1(&nums1), nums2(&nums2), idx(idx) {}
    
    reference operator*() const { return forward_as_tuple((*nums1)[idx], (*nums2)[idx]);  }
    IterPair& operator ++ () { idx++; return *this; }
    IterPair& operator -- () { idx--; return *this; }
    IterPair operator ++ (int) { IterPair tmp(*this); idx++; return tmp; }
    IterPair operator -- (int) { IterPair tmp(*this); idx--; return tmp; }
    int operator - (const IterPair& rhs) const { return idx - rhs.idx;   }
    IterPair operator + (int n) const { IterPair tmp(*this); tmp.idx += n; return tmp; }
    IterPair operator - (int n) const { IterPair tmp(*this); tmp.idx -= n; return tmp; }
    bool operator==(const IterPair& rhs) const { return idx == rhs.idx;  }
    bool operator!=(const IterPair& rhs) const { return idx != rhs.idx;  }
    bool operator<(const IterPair& rhs) const  { return idx < rhs.idx;   }
    bool operator<=(const IterPair& rhs) const { return idx <= rhs.idx;  }
};

namespace std{
template <>
void iter_swap(IterPair l, IterPair r)
{
    swap((*l.nums1)[l.idx], (*r.nums1)[r.idx]);
    swap((*l.nums2)[l.idx], (*r.nums2)[r.idx]);
}
}


class Solution {

    static int getQuality(const auto& quality_wage)
    {
        return get<0>(quality_wage);
    }
    
    static int getWage(const auto& quality_wage)
    {
        return get<1>(quality_wage);
    }
    
    static double getWageRatio(const auto& quality_wage)
    {
        return double(getWage(quality_wage)) / getQuality(quality_wage);
    }

    struct RatioLess
    {
        bool operator()(const auto& l, const auto& r) const noexcept { return getWageRatio(l) < getWageRatio(r); }
    };

    struct QualityLess
    {
        bool operator()(const auto& l, const auto& r) const noexcept { return getQuality(l) < getQuality(r); }
    };

public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k)
    {
        if (k == 1)
            return *min_element(wage.begin(), wage.end());

        auto n = quality.size();
        
        // split the arrays into 2 groups.
        // first group contains k elements with lowest ratio.
        // second group contains n-k elements with highest ratio.
        // time O(n) on average.
        nth_element(IterPair(quality, wage), IterPair(quality, wage, k), IterPair(quality, wage, n), RatioLess{});

        // calulate the sum of qualities of the first group.
        // time O(k).
        int hiredQuality = accumulate(quality.begin(), quality.begin() + k, 0);

        // calculate the cost of the first group.
        // time O(k).
        double hiredCost = hiredQuality * getWageRatio(*max_element(IterPair(quality, wage), IterPair(quality, wage, k), RatioLess{}));

        // make max heap from the first group of quality.
        // time O(k).
        make_heap(quality.begin(), quality.begin() + k);

        // sort the second group by ratio.
        // time O((n-k)*log(n-k)) on average.
        sort(IterPair(quality, wage, k), IterPair(quality, wage, n), RatioLess{});

        // iterate over the second group (sorted by ratio).
        // time O((n-k)*logk)
        for (int i = k; i < n; ++i)
        {
            auto q = quality[i];

            if (q < quality.front())
            {
                hiredQuality -= quality.front() - q;
                
                // time O(logk)
                pop_heap(quality.begin(), quality.begin() + k);
                quality[k-1] = q;
                push_heap(quality.begin(), quality.begin() + k);

                hiredCost = min(hiredCost, hiredQuality * getWageRatio(*IterPair(quality, wage, i)));
            }
        }

        return hiredCost;
    }
};
29900