来源：小红书笔试，难度中等（0528实习笔试真题解析）
小苯的文章浏览
小苯是小红书的忠实用户之一。
这天，在“小红书app”发了一篇文章后，收获了若干浏览量。但其中有人浏览了多次，小苯现在想知道所有人第一次浏览的先后顺序，请你帮帮他吧。
输入描述：
输入包含n+1行。
第一行一个正整数n($1<=n<=10^5$)，表示小苯拿到的浏览记录的记录条数。
接下来每行一个字符串s (长度在20)以内，表示id为s的用户此时浏览了一次小苯的文章。
输出描述：
输出包含若干行，每行一个字符串s，表示用户的id。按照每个浏览的用户第一次浏览的顺序输出。
样例输入：
1
2
3
4
5
6
7
8
9
|
8
qcjj
benh
qsmcgogo
qcjj
ducksajin
benh
ducksajin
acidlemon
|
样例输出：
1
2
3
4
5
|
qcjj
benh
qsmcgogo
ducksajin
acidlemon
|
提示:
共有以上5人点赞，按照第—次点的顺序输出即可。
分析
思路与代码
哈希表模拟即可，简单模拟。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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。
样例输入:
样例输出:
**提示:**选择第3个和第5个旧账号，并在第3个账号多次发文。
分析
思路与代码
比较典型的动态规划的题目，每个账号有三种状态：不发，发一次或者多发，那么按照dp套路来即可，比较简单，下面是记忆化搜索的代码。
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
31
32
33
34
35
36
37
38
39
|
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。
样例输入:
样例输出:
提示:
对于第一个笔记，当它赞数加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），那么如何判断当前帖子是否可以是最大的呢？
- 当前帖子的点赞数 like + x/2 + 1 是大于等于原帖子的最大值
- 剩余帖子的总点赞数 + x/2 的平均数小于等于 like + x/2 + 1.
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
31
32
33
34
35
|
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)))
|
