小红书春招实习笔试题解(0510)

type

status

date

slug

summary

📝 主旨内容

小红的碾压墙(数学)

题目描述：

小红是游戏《H炉》的一个主播。她经常去小红书发布关于H炉的卡牌研究攻略。

H炉有一张牌叫做碾压墙，可以消灭敌方最左边和最右边的随从，另一张牌叫做致命射击，可以随机消灭一个敌方随从。

如果小红使用两张致命射击恰好消灭了敌方最左边和最右边的随从（恰好造成了一张碾压墙的效果），就会有人在评论区发布“碾压墙” 。注意：两张致命射击的结算有先后顺序，即两张致命射击不会消灭同一个敌方随从。

现在有 n 个敌方随从，小红想知道她使用两张致命射击后，恰好造成一张碾压墙的效果的概率是多少。你的答案请四舍五入保留10位小数。

输入描述

第一行输入一个整数 n(2 ≤ n ≤ 10^6) 。

输出描述

输出一个实数表示答案(请四舍五入保留10位小数)。

样例输入

样例输出

提示

说明只有两个随从，必然造成碾压墙的效果。

输入

输出

💡

简单的排列组合问题，第一次打中最左边的概率是1/n，第二次打中最右边的因为打掉了一个所以概率是1/(n-1)。因为第一次打中最左边和最右边都是可以的，所以答案需要乘2

💡

注意python保留小数的写法

小红的精选笔记(思维，优先队列)

题目描述:

小红在小红书上面发布了n篇笔记，其中第i筒笔记的点赞数量为ai,评论数为bi。现在小红准备选择k筒笔记作为“精选笔记合集”，合集的优秀程度为:所有笔记点赞数之和乘以评论数的最小值。

现在小红想知道，最终台集最大的优秀度是多少?

输入描述

第一行输入两个正整数n,k,代表笔记的数量,以及小红准备选择的合集大小。

第二行输入n个正整教ai,代表每篇笔记的点赞数。第三行输入n个正整数bi,代表每篇笔记的评论数。

输出描述

一个正整数,代表最终最大的优秀度。

样例输入

样例输出

提示

选第二篇和第三篇即可。

💡

由于涉及到两个变量，很容易想到设计一个排序规则排个序就行，但是这里是涉及到一个变量的最小值和一个变量的求和，需要先固定一个变量，很明显需要固定取最小值的那个变量

💡

枚举一篇笔记作为评论的最小值，再找剩下的k-1篇笔记，需要评论数大于等于枚举的笔记，并且要浏览量大，这里可以用优先队列来完成

💡

如果对从小到大根据评论数量排序，那么堆初始化就是全部的笔记，每次枚举都需要经历删除和弹出操作，当k特别大的时候容易超时

💡

正难则反，我们排序后从最大的评论数开始枚举，这样对于优先队列来说，就只有入队操作，队列的长度最大为k，k个最大和也好维护，用最小堆实现

小红的点赞(二分，思维)

小红发布了n个笔记，每个笔记的点赞数为。小红观察到，每隔一段时间，某个笔记的点赞数就会加1。但是不会出现一个笔记点赞数连续增加的情况。也就是说，一个笔记赞数加1后，下一个加1的必然是另一个笔记。

现在小红想知道，对于每一个笔记，其赞数变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值是多少？

输入描述：

第一行输入一个正整数n，代表笔记的数量。

第二行输入n个正整数，代表每个笔记当前的赞数。

输出描述:

输出n行，每行输出一个整数，代表第i个笔记变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值。特殊的，如果第i个笔记永远无法变成赞数最多，则输出-1。

样例输入:

样例输出:

提示:

对于第一个笔记，当它赞数加1时，赞数达到了4，变成所有笔记赞数最多，此时赞数之和为4+1+4=9。对于第二个笔记，可以有以下增长方式:2->1->2->1->2->3->2，此时三个笔记的赞数都是5，赞数之和为15。对于第三个笔记，初始时它的赞数就是最多，此时赞数之和为3+1+4=8。

💡

首先，增加的次数一定是奇数。贪心地去考虑，第一次一定先给自身加，所以每次给自身增加轮次都是奇数，如果总次数是偶数的话那么会额外浪费一次给其他笔记点赞

💡

分析两种特殊情况，1.本来就是最大，那就不用加，答案就是原数组和。2.非最大值并且数组只有两个元素，那么较小的元素(如果不和最大值差1的话)这辈子都不可能是最大的，答案是-1

💡

n的范围是10^5，并且每个数都需要单独处理，说明每个数处理的复杂度需要控制在O(logn)级别。可以发现如果增加x是可行的，那么x+1(其实应该是x+2保证奇数)必然可行，那么问题就是有二段性的，综合以上两点不难得出应该用二分来解决

💡

二分的复杂度就是O(logn)，那么如何在O(1)的复杂度下判断枚举的增加次数是否可行呢？我们观察最坏的情况即可，如下图，设需要判断增加x次，对于4来说是否可行，那么4一定会加上x/2+1次(每个奇数轮次给4加一)，那么增加后的最大值就已经确定了，最坏情况下，要确保4最后依然是最大值，那么其余数字都是最大，再加一个(一定是加在非4上)就会爆炸，所以我们只需要判断增加后的数组和是否小于等于最坏情况下的数组和即可

💡

for循环内每次输出速度比一次性输出会慢，所以用数组存储每次的结果，最后一并组合输出一次

🤗 总结归纳

整体难度中等偏难，倒数两题有一定的思维量，很容易签到完坐牢

📝 主旨内容

小红的碾压墙(数学)

小红的精选笔记(思维，优先队列)

小红的点赞(二分，思维)

🤗 总结归纳

📎 参考文章