Greedy+make_heap vs 2nd largest||251ms beats 100%
IntuitionTo compute the increment for each pair (p,q)
q+1p+1​−qp​=q(q+1)q−p​
Then use Greedy to deploy the extraStudents for the pair (p,q) with the most increm
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo compute the increment for each pair $(p, q)$\n$$ \n\\frac{p+1}{q+1}-\\frac{p}{q}=\\frac{q-p}{q(q+1)}\n$$\nThen use Greedy to deploy the extraStudents for the pair $(p, q)$ with the most increment at each time; that is done by using `make_heap`. Python code is done by using `heapify` & `heapreplace`.\n\n2nd approach is using the observation by @Sergei. If the largest increment is much bigger than the 2nd one, there is a way to reduce the number of heap operations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Let `sum` denote the sum of ratio.\n2. Let `A` be the array containing the tuple `(increment, p, q)` which is  using C-array & declared as global variable.\n3. Use a loop to add `p/q` to `sum` & compute the increment $$ \n\\frac{p+1}{q+1}-\\frac{p}{q}=\\frac{q-p}{q(q+1)}\n$$. Set `A[i]=(inc, p, q)`. It costs O(n) of TC.\n4. Apply `make_heap` to `A[0:n]`; TC:O(n)\n5. Use a loop from `i=0` to `k-1` do the following\n```\npop_heap(A, A+n);// make the max inc to A[n-1]; TC: O(log n)\nauto [r, p, q] = A[n-1];\nif (r==0) break;// early stop\n            \n// Add the current inc to the sum; each ratio has the same weight\nsum += r;\n\n// Compute the new increment r2 for the pair (p+1, q+1)\ndouble r2= (double)(q - p) / ((q +1.0)* (q + 2.0));\n\nA[n-1]={ r2, p+1, q+1};// just update A[n-1] without push or pop\n\n// update the heap  after changing value for A[n-1]; TC:O(log n)\npush_heap(A, A+n);\n```\n6. return `sum/n`\n7. Python is done. But Python has **min heap by using heapq**. The changing sign trick is used. heapify & heapreplace are used. `heapreplace` is more efficient than heappop & heappush\n8. C++ priority_queue is done, please ref the link in th comments\n9. 2nd approach is using the observation by @Sergei. If the largest increment is much bigger than the 2nd one, there is a way to reduce the number of heap operations. The main idea is to find 1st largest 1, to make heap from other elements. Then 2nd largest one will be on the top. Between 1st& 2nd ones there are many operations for numerator+1 & denominator+1 without any heap operations such as pop & push. \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n+k\\log n)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(n)$\n# Code ||C++ using make_heap 251ms beats 100%|Python 897ms Beats 96.67%\n```cpp []\nusing info = tuple<double, int, int>;\ninfo A[100000];\nclass Solution {\npublic:\n    static double maxAverageRatio(vector<vector<int>>& classes, int k) {\n        const int n = classes.size();\n        double sum = 0.0;\n        int i = 0;\n        for (auto& pq : classes) {\n            int p = pq[0], q = pq[1];\n            sum += (double)p/q;\n            double inc=(double)(q - p) / (q * (q + 1.0));\n            A[i++]={inc, p, q};\n        }\n        \n        make_heap(A, A+n);\n        \n        for (int i = 0; i < k; i++) {\n            pop_heap(A, A+n);\n            auto [r, p, q] = A[n-1];\n            if (r==0) break;// early stop\n            \n            // Add the current inc to the sum\n            sum += r;\n            double r2= (double)(q - p) / ((q +1.0)* (q + 2.0));\n            A[n-1]={ r2, p+1, q+1};\n            push_heap(A, A+n);\n        }\n        \n        return sum / n;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```\n``` Python []\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], k: int) -> float:\n        n=len(classes)\n        sum=0\n        A=[]\n        for p,q in classes:\n            sum+=p/q\n            A.append(((p-q)/(q*(q+1)), p, q)) # change sign\n\n        heapify(A)\n\n        for _ in range(k):\n            (r, p, q)=A[0]\n            if r==0: break\n            sum-=r # change sign\n            r2=(p-q)/((q +1.0)* (q + 2.0))\n            heapreplace(A, (r2, p+1, q+1))\n        return sum/n\n```\n# C++ finds the 1st, 2nd largest increments\n```\nusing info = tuple<double, int, int>;\nvector<info> A;\nclass Solution {\npublic:\n    static inline double incr(int p, int q) {\n        return (q - p) / (q * (q + 1.0));\n    }\n    static double maxAverageRatio(vector<vector<int>>& classes, int k) {\n        const int n = classes.size();\n        A.resize(n);\n        double sum = 0.0;\n        for (int i = n - 1; i >= 0; i--) {\n            int p = classes[i][0], q = classes[i][1];\n            sum += (double)p / q;\n            A[i] = {incr(p, q), p, q};\n            if (A[i]>A[n-1]) swap(A[i], A[n-1]);//keep A[n-1] largest\n        }\n        make_heap(A.begin(), A.end()-1);\n\n        while (k>0) {\n            pop_heap(A.begin(), A.end()-1);\n            auto [r1, p1, q1]=A[n-1];\n            double r2=get<0>(A[n-2]);\n            sum+=r1;\n            int s=1;\n            double rr;\n            for(; s<k; s++){\n                rr=incr(p1+s, q1+s);\n                if (rr<r2) break;\n                else sum+=rr;// add rr to sum\n            }\n            k-=s; //decrease k by s\n            if (k==0) break;\n            A[n-1]=A[n-2];\n            A[n-2]={rr, p1+s, q1+s};\n        //    if (A[n-1]<A[n-2]) swap(A[n-2], A[n-1]);\n            push_heap(A.begin(), A.end()-1);\n        }\n\n        return sum / n;\n    }\n};\n\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++', 'Python3']