2023暑期实习-笔试-拼多多-算法实习生
公司：拼多多
岗位：算法实习生
笔试平台：牛客
考试题型：编程 4 道
考试时长：120分钟
考试时间：2023-03-12 19:00-21:00
多多的压缩编码II
描述
还原压缩后的字符串。
示例
示例1
输入
10a1b1c
输出
aaaaaaaaaabc
示例2
输入
1P2D1p2d1P1D1d
输出
PDDpddPDd
思路
直接模拟，遇到数字累计次数，遇到字母则追加到答案中。
代码
s = input()
ans = ''
cnt = ''
for c in s:
if c.isdigit():
cnt += c
else:
cnt = int(cnt)
ans += c * cnt
cnt = ''
print(ans)
多多的飞机大战游戏
描述
多多最近下载了一款飞机大战的游戏，多多可以通过游戏上的不同发射按键来控制飞机发射子弹：
按下A键，飞机会发射出2枚子弹，每个子弹会对命中的敌人造成1点固定伤害，但不能作用于同个敌人。
按下B键，飞机会发射出1枚子弹，子弹会对命中的敌人造成巨额伤害并瞬间将其秒杀。
多多是个游戏高手，总是能操控子弹命中想要命中的敌人。这个游戏—共有 T 个关卡，消灭当前关卡全部敌人后，发射出去多余的子弹会消失，游戏会自动进入下一个关卡。
假设每个关卡都会在屏幕中同时出现N个敌人，这N个敌人所能承受的伤害也已经知道。多多想知道，每个关卡自己最少按几次发射按键就可以将敌人全部消灭。
输入描述
第一行输入一个固定数字T（1<=T=1000）表示关卡的总数量，N（1<=N<=200）表示每个关卡出现的敌人数量。
接下来T行，每行有N个数字D1，D2，...，Dw（1<= Di <= 200）分别表示这N个敌人所能承受的伤害。
输出描述
结果共有N行，每行一个数字，分别表示对于这个关卡，最少按几次发射按键就可以将敌人全部消灭。
示例
输入
3 3
1 2 1
2 3 2
1 2 3
输出
2
3
3
说明
游戏共有3个关卡,每个关卡会出现3个敌人。
第一个关卡，先按下A建控制子弹消灭第1个和第3个敌人后,再按下B键消灭第二个敌人，所以最少按2次。
第二个关卡，按下3次B键分别消灭这3个敌人。
第三个关卡，按下3次B键分别消灭这3个敌人。也可以按3次A建,敌人剩余承受伤害的变化为：[1,2,3]->[1,1,2]->[0,0,1]->[0,0,0]
思路
贪心：优先使用A键，然后使用B键。如果敌人生命值等于1，统计生命值等于1的敌人数量，杀掉2个敌人需要使用1次A键；如果敌人生命值大于1，直接使用B键，需要1次按键。
代码
T, N = map(int, input().split())
for i in range(T):
D = list(map(int, input().split()))
cnt = 0
for j in D:
if j == 1:
cnt += 1
ans = N - cnt // 2
print(ans)
多多的团建计划
描述
多多君准备了三个活动（分别编号A、B和C)，每个活动分别有人数上限以及每个人参加的费用。
参加团建的有N个人(分别编号1~N），每个人先投票选择若干个意向的活动，最终每个人只能参加其中一个。
多多君收集完投票结果后，发现如何安排成为了大难题：如何在满足所有人的意向的情况下，使得活动的总费用最少。
于是多多君找到了擅长编程的你，希望你能帮助找到个合理的团建计划。
输入描述
第一行，一个整数N（1<=N<=100），代表准备参加活动的人数。
接下来N行，每行一个由 "ABC" 组成的字符串，其中第i行表示第i个人投票了哪几个活动。输入保证字符串非空，且由大写的 "ABC" 字符组成。
最后三行，每行两个整数，分别表示三个活动的人数上限以及每个人参加的费用。
输出描述
输出共2行
如果能满足所有人的要求，第一行输出 "YES"，第二行输出最少的总费用。
如果不能满足所有人的要求，第一行输出 "NO"，第二行输出最多能满足多少人。
示例
示例1
输入
5
A
B
C
AB
ABC
2 1
2 2
2 3
输出
YES
9
说明
可以满足所有人的要求，其中一种费用最少的方案：
A：{1, 4}
B：{2, 5}
C：{3}
总共需要费用：1∗2+2∗2+3∗1=9
示例2
输入
5
A
B
C
AB
AB
1 1
2 2
3 3
输出
NO
4
说明
无法满足所有人的需求，其中一种满足最多人的方案：
A：{1}
B：{2, 4}
C：{3}
共 4 人
思路
方法一：四维dp
方法二：最小费用最大流
代码
N = int(input())
d = {'A': 0, 'B': 0, 'C': 0}
for i in range(N):
s = input()
for j in s:
d[j] += 1
a, b, c = d['A'], d['B'], d['C']
# 待补充
多多的餐厅客流量
描述
多多君开了一家自助餐厅，为了更好地管理库存，多多君每天需要对之前的客流量数据进行分析，并根据客流量的平均数和中位数来制定合理的备货策略。
输入描述
第一行一个整数N,表示餐厅营业总天数(0<n<=200,000),< p=""></n<=200,000),<>
第二行共N个整数,分别表示第i天的客流量R:(0= R:1, 000, 000)。
输出描述
输出共两行：
第一行长度为N，其中第i个值表示前i天客流量的平均值；第二行长度为N，其中第i个值表示前i天客流量的中位数。
一共有N天，每天的客流量为 Ri，求第1天到第i天的平均数和中位数，结果四舍五入保留整数。
示例
输入
5
1 2 3 4 10
输出
1 2 2 3 4
1 2 2 3 3
思路
求数组的平均数参考前缀和，直接累加求和除以元素个数。
求数组的中位数可以参考：https://leetcode.cn/problems/find-median-from-data-stream/
这里提供一种使用二分查找插入的做法。
注意 Python 中 round 函数的四舍五入规则，记得在后面加上一个比长度略长的小数（例如0.000001），牛客上有类似的基础题。
代码
#软件开发2023笔面经##软件开发春招备战日记##拼多多笔试##拼多多##我的实习求职记录#
N = int(input())
R = list(map(int, input().split()))
avg = [0 for _ in range(N)]
med = [0 for _ in range(N)]
avg[0] = R[0]
med[0] = R[0]
s = R[0]
m = [R[0]]
for i in range(1, N):
s += R[i]
avg[i] = round(s / (i+1) + 0.000001)
left, right = 0, i
while left < right:
mid = (left + right) // 2
if m[mid] <= R[i]:
left = mid + 1
elif m[mid] > R[i]:
right = mid
m.insert(left, R[i])
if i % 2:
med[i] = round((m[i // 2] + m[i // 2 + 1]) / 2 + 0.000001)
else:
med[i] = m[i // 2]
for a in avg:
print(a, end=' ')
print()
for b in med:
print(b, end=' ')