算法leetcode

【贪心难题】力扣1792-最大平均通过率（堆贪心）

字数统计: 1.1k字   |   阅读时长: 4分
,

摘要: 堆贪心

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们回顾第 232 周赛 C 题。这是一个基于堆的贪心算法。

这种贪心的问题思维量还是挺大的，要找到贪心策略需要对问题细致分析，有时需要推一些公式。

有了贪心策略之后，如何在算法中维护贪心策略也是一个问题，其中堆是一种常见的方法，下面是堆贪心的题目的简单汇总：

$1 题目

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

1
2
3
4
5
提示：
1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105

示例 1：
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2：
输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

$2 题解

算法: 贪心、堆

所有班级的通过率 = 各个班级的通过率之和 / 班级数 = result / n。

每个班级有通过人数 pass 和总人数 total 两个信息。记第 i 个班级的通过率为 r，则有 r = pass / total，总通过率公式如下：

如果此时有一个额外的肯定通过的人，下面考察把他加到哪个班的收益最大: 假设此人加入了班级 i，则该班级的通过率变为 $(pass_{i} + 1)/(total_{i} + 1)$，收益为：

也就是从 n 个班级中选出 $\Delta$ 值最大的，将额外的人加入进入就可以了。对每个班级，除了 pass 和 total 以外，再维护一个 delta 信息，记录上述的这个值。

一共有 extraStudents 个额外的人，就执行 extraStudents 次插入操作，每次操作的过程如下:

1
2
先查询到 $\Delta$ 最大的班级
将 1 个额外的人加入，更新该班级的 pass, total, delta

支持以上操作的维护班级信息的数据结果用堆。

最后遍历所有班级的信息，组合出答案。

代码 (C++)

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
const double EPS = 1e-9;

struct ClassInfo
{
    int pass;
    int total;
    double delta;
    ClassInfo(int p, int t):pass(p),total(t)
    {
        delta = (total - pass) / (double)total / (total + 1);
    }
};

struct Cmp
{
    bool operator()(const ClassInfo& c1, const ClassInfo& c2) const
    {
        return c1.delta < c2.delta;
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        int n = classes.size();
        priority_queue<ClassInfo, vector<ClassInfo>, Cmp> pq;
        for(const vector<int>& info: classes)
        {
            pq.push(ClassInfo(info[0], info[1]));
        }
        while(extraStudents > 0)
        {
            ClassInfo p = pq.top();
            pq.pop();
            pq.push(ClassInfo(p.pass + 1, p.total + 1));
            --extraStudents;
        }
        double result = 0.0;
        while(!pq.empty())
        {
            result += double(pq.top().pass) / (pq.top().total);
            pq.pop();
        }
        return result / n;
    }
};
Share