Vermoshの探索日志

分类导航

LeetCode Record – 1 最大平均通过率

作者：

Vermosh

在

25 – 09 – 01

6月13日：刷 LeetCode，写不来。

7月13日：刷 LeetCode，写不来。

8月13日：刷 LeetCode，写不来。

8月31日：Vermosh 啊 Vermosh！你怎么能如此堕落！先前定下的刷题计划你都忘了吗？子曰：“吾日三省吾身。”不能再这样下去了！

9月1日：刷 LeetCode，写不来。

咳，总之就想开个专栏记录一下每日一题的思考过程.

今日题份，也是当上南山校长了(bs：

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

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

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

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

读题，第一反应是八成要用堆(heap),毕竟涉及到最小值操作，使用堆无疑是最容易想到的方法，那么问题就显而易见了：最小堆的确定指标是什么？

有一说一，我的第一反应是以当前班级的通过率为比较指标，想着拉最小的一把，拉着拉着均值或许就上去了，也就是二分中常见的最小值最大，所以第一稿的代码相当直接：

class ClassInfo implements Comparable<ClassInfo>{
    double pass;
    int passer;
    int total;
        
    ClassInfo(int passer, int total){
        this.pass = (double)passer / total;
        this.passer = passer;
        this.total = total;
    }
        
    @Override
    public int compareTo(ClassInfo other) {
        return Double.compare(this.pass, other.pass);
    }
}
// ...
while(curLowestClass.pass < classHeap.peek().pass){
    // 拉它一把
    curLowestClass = new ClassInfo(curLowestClass.passer + 1, curLowestClass.total + 1);
    --extraStudents;
}

看上去似乎没啥问题？如果看到这时和我当时的想法一样，那么恭喜恭喜，想法很美好，Error 没得跑。

为什么这样不对？

重新梳理一下题目，我们需要将 extraStudents 个额外学生分配到各个班级，以最大化所有班级的平均通过率。平均通过率定义为所有班级通过率之和除以班级数目。由于班级数目固定，最大化平均通过率等价于最大化所有班级的通过率之和。

每个班级的通过率函数为 $g_i(x_i) = \frac{\text{pass}_i + x_i}{\text{total}_i + x_i}$，其中 $x_i$ 是分配给班级 $i$ 的额外学生数。目标函数是 $\sum_i g_i(x_i)$，约束条件是 $\sum_i x_i = \text{extraStudents}$ 且 $x_i \geq 0$ 为整数。

我们开始的策略是选择当前通过率最小的班级进行贪心，但这并不总是最优，因为通过率小并不一定意味着边际增益大。边际增益取决于当前通过率和班级总人数等因素。

最简单的来说，考虑：

  • 一个通过率很低但总人数很大的班级，其边际增益可能很小。
  • 一个通过率较高但总人数很小的班级，其边际增益可能很大。

因此，贪心策略应基于边际增益（通过率增加量）而非当前通过率。

那么能严谨证明嘛？

对于函数 $g(x) = \frac{p + x}{t + x}$（其中 $p \leq t$，且 $x \geq 0$）：

一阶导数： $g'(x) = \frac{(t + x) \cdot 1 – (p + x) \cdot 1}{(t + x)^2} = \frac{t – p}{(t + x)^2} \geq 0$（因为 $t \geq p$），所以函数是递增的。

二阶导数： $g”(x) = \frac{d}{dx} \left( \frac{t – p}{(t + x)^2} \right) = -2 \frac{t – p}{(t + x)^3} < 0$（因为 $t – p \geq 0$ 且 $t + x > 0$），所以函数是凹的。

由于每个 $g_i(x_i)$ 都是凹函数，它们的和也是凹函数。对于凹函数最大化问题(under linear constraints)，贪心分配策略是最优的。

为什么对于凹函数最大化问题(under linear constraints)，贪心分配策略是最优的？

这其实可以通过 Karush-Kuhn-Tucker (KKT) 条件来解释。对于凸优化问题，KKT 条件提供了最优解的必要条件。在凹函数最大化下，这些条件也是充分的

  1. 那么在确定了以边际增益为比较指标后，算法的流程就很好确定了：$$\Delta_i = \frac{\text{pass}_i + 1}{\text{total}_i + 1} – \frac{\text{pass}_i}{\text{total}_i}$$
  2. 使用最大堆（优先队列）维护每个班级的边际增益。 对于每个额外学生：
    • 从堆中取出边际增益最大的班级。
    • 分配一个学生到该班级，更新其 pass 和 total。
    • 计算该班级新的边际增益，并重新插入堆中。
  3. 分配完所有额外学生后，计算总通过率之和并除以班级数，得到平均通过率。

所以给出 pass 代码如下：

import java.util.PriorityQueue;

class Solution {
    class ClassInfo implements Comparable<ClassInfo> {
        double passRatio;
        int pass;
        int total;
        
        ClassInfo(int pass, int total) {
            this.pass = pass;
            this.total = total;
            this.passRatio = (double) pass / total;
        }
        
        // 计算增加一个学生后的提升值
        double getImprovement() {
            return ((double) (pass + 1) / (total + 1)) - passRatio;
        }
        
        void addStudent() {
            this.pass++;
            this.total++;
            this.passRatio = (double) pass / total;
        }

        @Override
        public int compareTo(ClassInfo other) {
            // 按提升值降序排列（提升值大的优先级高）
            return Double.compare(other.getImprovement(), this.getImprovement());
        }
    }

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // 最大堆，按提升值降序排列
        PriorityQueue<ClassInfo> pq = new PriorityQueue<>();
        
        for (int[] cls : classes) {
            pq.offer(new ClassInfo(cls[0], cls[1]));
        }
        
        // 每次给提升最大的班级添加学生
        while (extraStudents > 0) {
            ClassInfo cls = pq.poll();
            cls.addStudent();
            pq.offer(cls);
            extraStudents--;
        }
        
        double sum = 0;
        while (!pq.isEmpty()) {
            sum += pq.poll().passRatio;
        }
        
        return sum / classes.length;
    }
}

我们需要一些优化

为了易于理解，第二次写的时候用了类，这会显著增加时间与空间开销，而浮点数存在舍入误差，考虑将其转化为乘法再进行比较，所以很明显的一些优化有：

import java.util.PriorityQueue;

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // 取消构造自定义类
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> {
                // 使用交叉相乘避免浮点运算
                long left = (long) (b[1] - b[0]) * a[1] * (a[1] + 1);
                long right = (long) (a[1] - a[0]) * b[1] * (b[1] + 1);
                return Long.compare(left, right);
            }
        );
        
        for (int[] cls : classes) {
            pq.offer(cls.clone());
        }
        
        while (extraStudents-- > 0) {
            int[] cls = pq.poll();
            cls[0]++;
            cls[1]++;
            pq.offer(cls);
        }
        
        double sum = 0;
        for (int[] cls : pq) {
            sum += (double) cls[0] / cls[1];
        }
        
        return sum / classes.length;
    }
}

当然还有优化空间，比如考虑使用自定义的比较器以减少重复计算：

import java.util.PriorityQueue;

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // 使用缓存提升值的比较器
        PriorityQueue<double[]> pq = new PriorityQueue<>(
            (a, b) -> Double.compare(b[0], a[0])
        );
        
        // 预计算所有提升值
        for (int[] cls : classes) {
            int pass = cls[0], total = cls[1];
            double improvement = ((double) (pass + 1) / (total + 1)) - ((double) pass / total);
            pq.offer(new double[]{improvement, pass, total});
        }
        
        while (extraStudents-- > 0) {
            double[] current = pq.poll();
            int pass = (int) current[1] + 1;
            int total = (int) current[2] + 1;
            double newImprovement = ((double) (pass + 1) / (total + 1)) - ((double) pass / total);
            pq.offer(new double[]{newImprovement, pass, total});
        }
        
        double sum = 0;
        for (double[] cls : pq) {
            sum += (double) cls[1] / cls[2];
        }
        
        return sum / classes.length;
    }
}

问了下 ai，它给出了一个很有意思的思路，通过导数值批量增加某一班级的人员，减少总的增加次数

import java.util.PriorityQueue;

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> {
                // 使用导数信息进行批量比较
                double derA = derivative(a[0], a[1]);
                double derB = derivative(b[0], b[1]);
                return Double.compare(derB, derA);
            }
        );
        
        for (int[] cls : classes) {
            pq.offer(cls);
        }
        
        // 批量处理：一次分配多个学生给提升最大的班级
        while (extraStudents > 0) {
            int[] bestClass = pq.poll();
            
            // 计算这个班级最多可以分配多少学生
            int maxToAdd = Math.min(extraStudents, calculateOptimalAdd(bestClass[0], bestClass[1]));
            bestClass[0] += maxToAdd;
            bestClass[1] += maxToAdd;
            extraStudents -= maxToAdd;
            
            pq.offer(bestClass);
        }
        
        double sum = 0;
        for (int[] cls : pq) {
            sum += (double) cls[0] / cls[1];
        }
        
        return sum / classes.length;
    }
    
    private double derivative(int pass, int total) {
        // 通过率的导数，用于判断提升速度
        return (double) (total - pass) / (total * total + total);
    }
    
    private int calculateOptimalAdd(int pass, int total) {
        // 启发式：当提升值降到一定程度时停止批量分配
        return Math.min(100, (int) Math.sqrt(total)); // 经验值
    }
}

不过这个在精度上有些许问题，而且基于经验的启发式阈值往往不是最优方案，事实也证明在提交时卡用例了。

以上

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

更多文章