leetcode_1792 最大平均通过率

1. 题意

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

最大的平均通过率。

最大平均通服务器托管网过率

2. 题解

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

d

i

f

f

diff

diff为

n

+

1

m

+

1

−

n

m

=

m

−

n

m

(

m
服务器托管网

+

1

)

frac{n+1}{m+1} – frac{n}{m} = frac{m -n}{m(m + 1)}

m+1n+1​−mn​=m(m+1)m−n​

我们可以通过维护班级的

d

i

f

f

diff

diff值的最大堆来解决这个问题。

由于

0

≤

n

≤

m

≤

1

e

5

0 le n le m le 1e5

0≤n≤m≤1e5

在比较两个班级的

d

i

f

f

diff

diff值的时候可以换为乘法

即判断

(

m

0

−

n

0

)

∗

m

1

(

m

1

+

1

)

(m0​−n0​)∗m1​(m1​+1)(m1​−n1​)∗m0​(m0​+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(vectorvectorint>>& classes, int extraStudents) {

        std::priority_queueclassRate> 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();
    }
};

2.2 解法二

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 机顶盒替换遥控器

前提盒子有root权限，可以adb 可以用一个盒子的key.xml 文件替换到另外一个盒子，这样2个盒子公用一个遥控器 adb push /key.xml /etc/key.xml 这样去覆盖机顶盒之前的遥控器代码 服务器托管，北京服务器托管，服务器租用 ht…