leetcode_1792 最大平均通过率

1. 题意

给定一个班级数组，每个班级包括总人数和通过人数。现在可以加入k个通过的学生到任意班级，求

最大的平均通过率。

最大平均通过率

2. 题解

假设某一班级总人数为m, 通过人数为n,则加入一个通过的学生对通过率的增加$diff$为

$$\frac{n+1}{m+1}-\frac{n}{m}=\frac{m-n}{m(m+1)}$$

我们可以通过维护班级的$diff$值的最大堆来解决这个问题。

由于$0\le n\le m\le 1e5$

在比较两个班级的$diff$值的时候可以换为乘法

即判断
$$(m_0-n_0)\ast m_1(m_1+1)<(m_1-n_1)\ast m_0(m_0+1)$$
的布尔值即可

2.1 解法1

优先队列

class Solution {

    struct classRate {


        classRate(int a,int b):pass(a),total(b) {

        } 
    
        bool operator <( const classRate &b) const{

            long long a1 = 1ll * (total - pass) * (b.total) * (b.total + 1);
            long long a2 = 1ll * (b.total - b.pass) * (total) * (total + 1);

            return a1 < a2;
        }
        int  total;
        int  pass;
    };

public:
    double 
    maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

        std::priority_queue<classRate> rPq;

        for(auto &v:classes) {

            classRate elm(v[0], v[1]);

            rPq.push(elm);
        }

        int i = 0;
        while (i < extraStudents) {

            classRate cur = rPq.top();
            rPq.pop();

            cur.total += 1;
            cur.pass += 1;

            rPq.push(cur);

            i++;
        }

        double res = 0;
        while (!rPq.empty()) {
            classRate cur = rPq.top();
            rPq.pop();

            res += (double) cur.pass / cur.total;
        }

        return res/classes.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

2.2 解法二

中位数分治，暂时还没看懂。先放一个题解在这里吧。
中位数分治