比亚迪，学历大于一切

吴师兄学算法 · 公众号 · · 2024-04-13 16:23

正文

大家好，我是吴师兄。

前几天在牛客网上刷到一个帖子， “吐槽”了在比亚迪里面学历与晋升之间的博弈 。

他曾在比亚迪工作，入职时级别为G3/F1，但在三年内看来，升职到E1的可能性并不高。与此同时，一些学历较好的硕士应届生却可以直接以E1级别进入比亚迪。并且，比亚迪的职级倒挂更加明显，因为这种倒挂不仅仅是在薪资上，更体现在职级晋升的机会上。

进而推断出 在比亚迪，学历大于一切 。

如果一家公司只看重员工的学历背景，而忽视了他们的实际工作能力和贡献，那么很可能会错失许多优秀人才，影响到公司的长远发展。

除了对于晋升机会的影响外，这种以学历为主导的职级制度也可能带来其他一些负面影响。比如，可能会造成“新人优待”现象，即新员工凭借着较高的学历直接进入高级别职位，而忽视了老员工多年的工作经验和努力。这种情况不仅会降低老员工的工作积极性，也会造成团队内部的不和谐和紧张气氛。

好像互联网行业这种现象比较少，其它行业比如传统制造行业多多少少有这种苗头，大家是怎么看的？

继续今天的算法学习，来一个简单的算法题： 灯泡开关 。

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

这题的代码很简单，关键是证明。

假设结论 “当灯泡数目为 n-1 时，经过 n-1 轮后，最后有剩下 floor(sqrt(n-1)) 个灯泡是亮着的” 成立，用数学归纳法证明，需要考虑

n = 1 时，第 1 个灯泡经过 1 轮后从关变到开，上述结论显然成立。故证明的重点是，考虑灯泡数目取 n 时，结论 “当灯泡数目为 n 时，经过 n 轮后，最后有剩下 floor(sqrt(n)) 个灯泡是亮着的” 是否成立。

当灯泡数目为 n 时，考虑前 n-1 个灯泡的行为：

经过 n-1 轮后，前 n-1 个灯泡的行为和 考虑灯泡数目为 n-1 时经过 n-1 轮后的行为是完全一致的 ，故此时有 floor(sqrt(n-1)) 个灯泡是亮着的。
在第 n 轮中，只有第 n 个灯泡进行了切换，故前 n-1 个灯泡会维持存在 floor(sqrt(n-1)) 个灯泡是亮着的情况。

考虑最后一个灯泡，即第 n 个灯泡在 n 轮中的行为。

注意到，当且仅当 i 是 n 的因数时，第 n 个灯泡在遇到第 i 轮的时候会切换状态。考虑 n 的因数个数

因数总是成对出现的 ，假设 i 为 n 的因数，那么 n/i 一定是 n 的因数。即灯泡会在第 i 轮和第 n/i 轮，都会进行状态切换。

根据 i == n/i 可以计算出， i^2 == n 。我们可以得出结论：当且仅当 n 为某个正整数 i 的平方，即当 n 为一个完全平方数时，第 n 个灯泡经过 n 轮会经过奇数次状态转换，最终的状态为开。

令 A 和 B 是满足 A^2 <= n-1 <= B^2 和 A+1 = B 成立的两个正整数，即 n-1 是位于两个相差为 1 的正整数 A 和 B 的平方 A^2 和 B^2 之间的一个整数。显然 A = floor(sqrt(n-1)) 。

我们将考虑前 n-1 个灯泡和第 n 个灯泡的情况结合起来，计算经过 n 轮之后状态为开的灯泡的总数。若

那么 n 的最终状态为关，最终亮着的灯泡数为前 n-1 个灯泡亮着的数目，即 floor(sqrt(n-1)) 。
由于 n 不是完全平方数，那么 A^2 <= n-1 < n < B^2 成立，此时存在 A = floor(sqrt(n)) 成立，故 floor(sqrt(n-1)) = floor(sqrt(n)) 成立。
因此，对于 n 个灯泡经过 n 轮，最终会有 floor(sqrt(n)) 个灯泡亮着，结论成立。