[C++] Explained Priority Queue | Greedy Solution | Find the Delta
There are few incorrect approaches:\n1. Choosing the smallest class size\n2. Choosing the smallest pass size\n3. Choosing the least pass ratio\n\nInstead, the c
There are few incorrect approaches:\n1. Choosing the smallest class size\n2. Choosing the smallest pass size\n3. Choosing the least pass ratio\n\nInstead, the correct approach is:\n**Find the difference**, namely the delta. \n\nFor example, even though `1/2` and `10/20` has the same ratio. However, `1/2`\'s delta is equal to `(1+1)/(2+1)-1/2`, which is much greater than `(10+1)/(20+1)-10/20`. \n\nTherefore, we always greedily select the one with the greatest delta.\n\nWe can acheive this using a max heap. In C++, we can use the **priority queue**.\n\n[C++]: \n\n```\nstruct cmp{\n    bool operator()(pair<int,int> a, pair<int,int> b){\n        double ad = (a.first+1)/(double)(a.second+1) - (a.first)/(double)a.second;\n        double bd = (b.first+1)/(double)(b.second+1) - (b.first)/(double)b.second;\n        return ad < bd;\n    }\n};\n\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        double acc = 0;\n        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> que;\n        for(vector<int> i: classes)\n            que.push(make_pair(i[0],i[1]));\n        while(extraStudents--){\n            pair<int,int> cur = que.top(); que.pop();\n            cur.first++, cur.second++;\n            que.push(cur);\n        }\n        while(!que.empty()){\n            pair<int,int> cur = que.top(); que.pop();\n            acc += cur.first / (double) cur.second;\n        }\n        return acc / (double) classes.size();\n    }\n};\n```\n
['C', 'Heap (Priority Queue)', 'C++']