0528 小红书实习笔试真题 答案及解析_小红在小红书上发布n篇笔记,其中第i篇笔记的点赞数是ai,小红观察到,每隔一段时间

第一题 小苯的文章浏览

小苯是小红书的忠实用户之一。

这天，在“小红书app”发了一篇文章后，收获了若干浏览量。但其中有人浏览了多次，小苯现在想知道所有人第一次浏览的先后顺序，请你帮帮他吧。

输入描述：

输入包含n+1行。

第一行一个正整数n()，表示小苯拿到的浏览记录的记录条数。

接下来每行一个字符串s (长度在20)以内，表示id为s的用户此时浏览了一次小苯的文章。

输出描述：

输出包含若干行，每行一个字符串s，表示用户的id。按照每个浏览的用户第一次浏览的顺序输出。

样例输入：

8
qcjj
benh
qsmcgogo
qcjj
ducksajin
benh
ducksajin
acidlemon

样例输出：

qcjj
benh
qsmcgogo
ducksajin
acidlemon

提示:

共有以上5人点赞，按照第—次点的顺序输出即可。

思路与代码

哈希表模拟即可，简单模拟。

def main():
    n = int(input())  
    seen = set()      
    ans = []          
 
    for _ in range(n):
        s = input()  
        if s in seen:
            continue
        seen.add(s)
        ans.append(s)
    
    for e in ans:
        print(e)
 
if __name__ == "__main__":
    main()

第二题 小苯的粉丝关注

小苯是“小红书app”的忠实用户，他有n个账号，每个账号粉丝数为。

这天他又创建了一个新账号，他希望新账号的粉丝数恰好等于x。为此他可以向自己已有账号的粉丝们推荐自己的新账号，这样以来新账号就得到了之前粉丝的关注。

他想知道，他最少需要在几个旧账号发“推荐新账号”的文章，可以使得他的新账号粉丝数恰好为x，除此以外，他可以最多从中选择一个账号多次发“推荐新账号”的文章。

(我们假设所有旧账号的粉丝们没有重叠，并且如果在第i个旧账号的粉丝们推荐了新账号，则新账号会直接涨粉 下取整个，而如果小苯选择在第 i个旧账号中多次推荐新账号，那么新账号就可以直接涨粉。)

输入描述:

输入包含2行。 第一行两个正整数 n, x(1 ≤ n, k ≤ 100)，分别表示小苯的旧账号个数，和新账号想要的粉丝数。 第二行n个正整数 (1 ≤ ≤ 100)，表示小苯每个旧账号的粉丝数。

输出描述:

输出包含一行一个整数，表示小苯最少需要向多少个旧帐号推荐新账号，如果无法做到，输出-1。

样例输入:

5 8
1 2 3 4 10

样例输出:

2

提示:选择第3个和第5个旧账号，并在第3个账号多次发文。

思路与代码

比较典型的动态规划的题目，每个账号有三种状态：不发，发一次或者多发，那么按照dp套路来即可，比较简单，下面是记忆化搜索的代码。

import sys
 
def dfs(i, x, extra, n, a, memo):
    if x == 0:
        return 0
    if i >= n:
        return n + 1
    if memo[i][x][extra] != -1:
        return memo[i][x][extra]
 
    no = dfs(i + 1, x, extra, n, a, memo)
    one = n + 1
    if x >= a[i] // 2:
        one = dfs(i + 1, x - a[i] // 2, extra, n, a, memo) + 1
    multi = n + 1
    if x >= a[i] and not extra:
        multi = dfs(i + 1, x - a[i], True, n, a, memo) + 1
 
    memo[i][x][extra] = min(no, one, multi)
    return memo[i][x][extra]
 
def main():
    input = sys.stdin.read
    data = input().split()
 
    n = int(data[0])
    x = int(data[1])
    a = list(map(int, data[2:2+n]))
 
    memo = [[[-1 for _ in range(2)] for _ in range(x + 1)] for _ in range(n + 1)]
 
    ans = dfs(0, x, False, n, a, memo)
    if ans == n + 1:
        print(-1)
    else:
        print(ans)
 
if __name__ == "__main__":
    main()

小红的点赞

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

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

输入描述：

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

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

输出描述:

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

样例输入:

3
3 1 4

样例输出:

9
15
8

提示:

对于第一个笔记，当它赞数加1时，赞数达到了4，变成所有笔记赞数最多，此时赞数之和为4+1+4=9。

对于第二个笔记，可以有以下增长方式:2->1->2->1->2->3->2，此时三个笔记的赞数都是5，赞数之和为15。

对于第三个笔记，初始时它的赞数就是最多，此时赞数之和为3+1+4=8。

思路与代码：

二分答案。

结论1：如果说点赞次数x是偶数，那么是不如x-1的（因为会导致其他的贴子点赞数+1）

结论2：如果点赞x可以，那么x+1就肯定可以，因此具有二段性，可以进行二分。

我们需要判断将某个帖子的点赞数最多的时候，我们二分点赞的次数，假设说点赞次数是x，那么当前帖子最多可以被点击x/2 + 1次（如果x是偶数的话，我们直接将x-1），那么如何判断当前帖子是否可以是最大的呢？

1. 当前帖子的点赞数 like + x/2 + 1 是大于等于原帖子的最大值
2. 剩余帖子的总点赞数 + x/2 的平均数小于等于 like + x/2 + 1.

n = int(input())
likes = [int(x) for x in input().split()]
MX = max(likes)
SUM = sum(likes)
res = [0]*n
 
# 总点赞数是x的时候，是否可以使得i变为最大值
def check(x,i):
    # 如果x是偶数，我们要让他-1变为奇数
    if x%2==0: x-=1
    diff = x//2 + 1 # 需要增加的点赞数
    cur = SUM - likes[i] + (x-diff) # 排除当前帖子后，其他帖子点赞后的总数
    if diff + likes[i] >= MX and (like[i]+diff)*(n-1) >= cur: return True
    return False
 
for i,like in enumerate(likes):
    # 将当前的like变为最大
    if len(likes) == 2 and like < mx-1:
        res[i] = -1
        continue
    if like == MX:
        res[i] = SUM
        continue
 
    # 如何让当前的like变为最大？
    # 如果总点赞数是 x的时候是可行的，那么此时 x+1，x+2，x+3...都是可行的（x必然是奇数）
    # 因此，总点赞数是具有二段型的，可以进行二分。
    l,r = 1, 10**9
    while l < r:
        mid = (l+r)>>1
        if check(mid,i): r = mid
        else: l = mid + 1
    res[i] = SUM + r
 
print('\n'.join(map(str,res)))

---