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

/*
    Lets assume we have selected k workers
    lets say their minWages and qualities are Wi and Qi
    as we have to give every worker min wage Wi and also need to take care of quality Ratio, we have to select one worker as reference worker to make payment to workers in ratio

    Lets say reference worker have Wr and Qr min wage and quality repectively
    suppose we made a payment Pr to this worker

    payment made to worker i should be as:
    Pi = Qi * Pr/Qr

    as pr min wage condition : Pi should be greater than or equal to Wi

    total payment made to k workers: Q1*Pr/Qr + Q2*Pr/Qr + Q3*Pr/Qr + ....... k workers
    total_payment =  Pr/Qr (Q1+Q2+Q3+.....k workers)
    Total_payment: reference_Ratio * sigma(quqlities)
    To minimise total ratio: minimise ratio or minimise sum of qualities or both


    WHAT CAN WE MINIMISE AND WHAT CAN NOT AND WHY ?

    Now few observations: as payment to worker i is : Qi * Pr/Qr >= Wi
    to minimise, give Wage Wr to the reference worker as its payment
    so Wr/Qr * Qi >= Wi
    this means reference should be selected as the one having maximum ratio of Wage/quality
    because, it is safest side, as now we dont want to decrease its wage but we can increase others wage according tto this ratio
    minimising the ratio might lead to incorrect results 

    So out of k selected: reference_ratio should be taken which is maximum out of those k ..........(1)
    Sum of qualities of these k selected should be minimum ......(2)

    
    how to solve this, we need two things: 
    1. sorted array of increasing ratio (current ration will be considered as reference) and all less than it (giving minimu qualities sum) are other
    2. max heap of size k which will hlp me to remove the worker with higest quality

    as we iterate over this sorted increasing Wage/Quality array : 
    everyTime we consider current as reference 9maximum ratio so far), and we take all other ratios (k) less than current, which can give me a minimum qualities sum,
    Keep updating the answers for every iteration (for every reference)

    for a refernce ratio: find other k-1 workers giving me mimimum_quality_sum THAT'S IT

*/


class Solution {
public:
    struct cmp
    {
        bool operator()(pair<double,int>& p1, pair<double,int>& p2) {
            return p1.second < p2.second; //last element of vector should be maximum for maxheap
        }
    };

    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<pair<double,int>> vi;
        for(int i=0, n=quality.size(); i<n; i++) {
            vi.push_back(make_pair((double)wage[i]/quality[i], quality[i]));
        }

        sort(vi.begin(), vi.end(), [](pair<double,int>& p1, pair<double,int>& p2) {
            return p1.first < p2.first;
        });


        priority_queue<pair<double,int>, vector<pair<double,int>>, cmp> maxh;

        int qualitySum=0;
        double ans=DBL_MAX;

        for(auto it: vi) {
            double ratio = it.first; //reference
            qualitySum += it.second, maxh.push(it);

            if(maxh.size() > k) {
                qualitySum -= maxh.top().second, maxh.pop();
            }

            if(maxh.size()==k) ans=min(ans, ratio*qualitySum);
        }

        return ans;



    }
};
30100