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个数字D₁，D₂，...，Dw（1<= D_i <= 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），每个人先投