LeetCode周赛刷题

2021-03-17

1、最大平均通过率

题意:

有 n 个班级,每个班级有及格人数和全部人数,通关率为及格人数/全部人数,先有 n 次操作,每次操作可以将某个班级里增加一个必定合格的人数,问最大的平均通关率是多少,平均通关率是指所有通关率的总和除以个数,

思路
优先队列 + 结构体是最容易想到的,预处理将每个班级对总体的贡献放入队列中,即假设 a 为总人数,b 及格人数即为:

(b+1)/(a+1)-b/a=a-b/(b+1)*b

而这个值越大证明他对总体的贡献越大,而优先队列默认满足的是单调递减即大根堆,因此需要将分子换成 b-a 即可构造出含义上的小根堆

代码

struct st{
    
    
    int a,b;
    double pi;
    bool operator <(const  st &W)const{
        return pi<W.pi;
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& cs, int cnt) {
        int len=cs.size();
        priority_queue<st>q;

        for(int i=0;i<len;i++) {
            int b=cs[i][0];
            int a=cs[i][1];
            double pi=b*1.0/a;
            q.push({a, b,(a - b) / (a * (a + 1.0))});
        }
         double ans=0;
        while(cnt--){
            auto item=q.top();
            q.pop();
            int a=item.a+1;
            int b=item.b+1;
            q.push({ a, b,(a - b) / (a * (a + 1.0))});
        
        }


        while(q.size()) {
            auto item=q.top();
            q.pop();
            int a=item.a;
            int b=item.b;
            ans+=b*1.0/a;
        }
       
        return ans/len;
    }
};

标题:LeetCode周赛刷题
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/03/17/1615987853519.html