Algorithm
lc1792_最大平均通过率
示例一可以知道不是简单得堆加到最小的比率值，而是需要考虑总数等因素
应该可以认为每一个优秀同学的加入都是一次单独的贪心操作，所以感觉可以每次都贪心处理
而每一次贪心，都可以看成小数点后面的5位数字的增长最大值
就是说，平均的班级数是固定的，需要增大最大总值，才能增大最大平均数，那就是遍历班级数，然后得到最大增长的小数点值
但是这样复杂度好像达到1e10了…不知道会不会超时…想想如何优化—应该是需要数学公式优化
(n+1)/(m+1) - n/m 要达到最大值，需要n,m在一个什么关系
(nm+m-nm-n)/((m+1)m) = (m - n)/(mm+m) 也就是m要尽量小，然后m-n又要尽量大，这样复杂度好像还是没有降低…
看看题解如何思考…
看题解的过程中想到用排序
后面看到题解发现用了一个优先队列…确实妙，自己比较接近答案了，下次得更近一步，嗯嗯
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
|
class Solution {
public:
struct Ratio {
int pass, total;
bool operator < (const Ratio& oth) const {
return (long long) (oth.total + 1) * oth.total * (total - pass) < (long long) (total + 1) * total * (oth.total - oth.pass);
}
};
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
priority_queue<Ratio> q;
for (auto &c : classes) {
q.push({c[0], c[1]});
}
for (int i = 0; i < extraStudents; i++) {
auto [pass, total] = q.top();
q.pop();
q.push({pass + 1, total + 1});
}
double res = 0;
for (int i = 0; i < classes.size(); i++) {
auto [pass, total] = q.top();
q.pop();
res += 1.0 * pass / 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
|
func maxAverageRatio(classes [][]int, extraStudents int) (ans float64) {
h := hp(classes)
heap.Init(&h)
for ; extraStudents > 0; extraStudents-- {
h[0][0]++
h[0][1]++
heap.Fix(&h, 0)
}
for _, c := range h {
ans += float64(c[0]) / float64(c[1])
}
return ans / float64(len(classes))
}
type hp [][]int
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return (a[1]-a[0])*b[1]*(b[1]+1) > (b[1]-b[0])*a[1]*(a[1]+1) }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (hp) Push(interface{}) {}
func (hp) Pop() (_ interface{}) { return }
|
Review
【TED演讲】关于死亡，乌鸦行为观察
对于乌鸦的死亡，其他乌鸦有如下的一些表现：
- 把死联系成危险，以后尽量少来这个地方 (我们可以学到借鉴他人的经验)
- 对于近亲的死亡，更多的是哀悼和梳理
- 对于陌生乌鸦的死亡，表现出攻击性，性冲动 （感觉像是一种感觉很晦气的感觉，然后想让本身族群延续后代)
Tips
字节开源的K8s存储KubeBrain
是对etcd的一个精简化的改造，其中我能看到的一些通用思想的提炼:
- 用分布式租约锁来简化选主
- 把网络通信改造成内存读取来提高性能
Share-开源分布式存储学习选择
决定先从存储前辈的回答中开始深入这三个项目先:
- JuiceFS，开源社区关注度提升很快，已有不少大厂用在生产环境上了。全球公有云上都有云服务，开箱即用。
- CubeFS（CubeFS），之前叫 ChubaoFS，最早诞生于京东内部。
- SeaweadFS（SeaweedFS），最初是对象存储，基于 Haystack 架构，最近两年加入了更多功能，包括 POSIX 支持。
自己看了一下CNCF中的只有CubeFS，加上CubeFS是OPPO主导的，所以可以先看CubeFS，其次是最近开源的JuiceFS
Juicefs官方文档
CubeFS官方文档
看了一下简介和架构，发现JuiceFS是类似于一个中间件，元数据和数据存储都是要套接其他数据库或者原来有的一些数据存储方案，而CubeFS是完全自研的一个架构设计，所以对于学习贡献，优先针对CubeFS进行。