用 Python 帮助腾蛇救璇玑 (阿里 2020.8.26 笔试第二题)

璇玑 (阿里 2020.8.26 笔试第二题)"/>

用 Python 帮助腾蛇救璇玑 (阿里 2020.8.26 笔试第二题)

用 Python 帮助腾蛇救璇玑

天墟堂贼人掳走了璇玑，只留下了神剑定坤。腾蛇神君得知后大怒，拿起定坤就冲进天墟堂救人。根据事先得到的情报，敌人总共有 n 人。可是来时匆忙，腾蛇只带了神剑定坤，剑的耐久度为 m。腾蛇生性好战，嫉恶如仇，恨不得杀光天墟堂贼人。可是腾蛇又不想过度损耗定坤，因此需要设计一个最优方案。已知天墟堂贼人等级分明，高等级的天墟堂贼人携带武器，低等级的则赤手空拳。因此每个贼人拥有的特性可以用 a, b 表示，a 表示杀死该贼人需要消耗定坤 a 点耐久度，如果贼人赤手空拳，则 b 为 0；如果携带武器，腾蛇就可以使用贼人的武器再杀死 b 个贼人。腾蛇希望在保证尽可能多地杀死贼人的情况下，尽可能少地损耗定坤。腾蛇神君头脑简单，因此向各位少侠求助，希望各位能给他提供一个最优方案，助他救出璇玑。

输入

1. n, m：n 表示天墟堂贼人数目，m 表示定坤耐久度
2. a, b: a 表示杀死该贼人需要消耗定坤 a 点耐久度，b 表示可以使用贼人的武器再杀 b 个贼人。为方便起见，所有的 a 和 b 都分别放在列表 A 和 B 中。

输出
返回值为杀死的贼人数目和神剑定坤的损耗度

样例展示
输入：
n, m = 5， 10
A = [4, 2, 4, 5, 10]
B = [0, 0, 1, 1, 1]
输出：
5， 6

Python 代码

n, m = 5, 10
A = [4, 2, 4, 5, 10]
B = [0, 0, 1, 1, 1]
##out = 5, 6C0 = sorted([(x, y) for x, y in zip(A, B)], key = lambda x : x[0])
C1 = []##首先只考虑自己杀怪的情况
kill_by_self = 0
cost_by_self = 0for a, b in C0:if cost_by_self + a <= m:kill_by_self += 1cost_by_self += aif b > 0:C1.append((a, b))kill = kill_by_self
cost = cost_by_self##首先判断有武器的怪物存不存在
if C1:         ##再考虑先杀第一个有武器的怪物的情况if m >= C1[0][0]:##杀第一个带武器的怪kill = 1cost = C1[0][0]##把第一个被杀的怪从C0里去掉，防止接下来再被遍历到C0.remove(C1[0])##计算还需要自己杀的怪的数量（前面已经杀了一个了）to_kill_by_self = n - sum(B) - 1##从C0里面选择要自己杀的怪物for i in range(to_kill_by_self):if cost + C0[i][0] <= m:kill += 1cost += C0[i][0]else:break##计算能杀的怪物的数量,即自己杀的和用怪物的武器杀的kill += sum(B)##现在判断只自己杀怪和考虑用怪物武器杀怪的优劣if kill_by_self > kill:kill = kill_by_selfcost = cost_by_selfelif kill_by_self == kill:if cost_by_self < cost:cost = cost_by_selfelse:kill = kill_by_selfcost = cost_by_selfprint('number of killed enemies: {:d}, used durability: {:d}'.format(kill, cost)

更多输入输出样例

##example 2
n, m = [6, 10]
A = [1, 2, 4, 3, 8, 9]
B = [0, 0, 0, 0, 1, 1]
##out = 4, 9##example 3
n, m = [5, 7]
A = [4, 2, 8, 8, 10]
B = [0, 0, 1, 1, 1]
##out = 2, 6