第一题：一个项目组有n人，所有人的能力表示为数组A，现有一任务M，M为完成该任务所需要的能力。可以分成多个小组完成，每个小组包含k人（1<=k<=n)，设小组中能力最强者的能力为Ai_max,该小组需满足k*Ai_max>=M，求最多分成多少个小组同时完成任务M。思路：比较简单，略。def max_groups_to_complete_task(A, M): # 首先，将能力数组A按升序排序 A.sort(reverse=True) # 初始化小组数为0 groups = 0 # 迭代数组A，形成小组 n = len(A) i = 0 left = 0 right = n - 1 while left <= right: cur_sum = 0 add_item = A[left] while left <= right: cur_sum += add_item if cur_sum >= M: groups += 1 left += 1 break right -= 1 return groups# 示例A = [82, 45, 37, 121, 55]M = 100result = max_groups_to_complete_task(A, M)print("最多可以分成 {} 个小组同时完成任务M。".format(result))第二题：我打算买些糖果，A数组是需要每类糖果的数量，B数组是每类糖果可以打折销售的最小数量。商店里每类糖果一颗2元，所购买的糖果总数达到一定数量后，某个种类的糖果将降价到1元销售。求最后所需花费的金额。如A=[ 2, 3, 2, 1], B=[ 1, 3, 4, 1],下标0~3，其中，先买一颗第2类糖果，花费2元，第2类糖果还剩2-1=1颗；此时，第0类和第3类都可以折扣购买，共花费3元；然后，已购买数量为4颗，则第1类和第2类糖果同样可以折扣购买，花费4元。共花费9=2+3+4。思路：使用2元单价购买所有糖果的花费减去用1元折扣价购买的糖果数量即为所求。用字典键代表该类糖果折扣数量要求，值代表该类糖果所需数量。# 将字典的键统一减少一个值def minusKey(dic, minus_value): new_dic = {} for key, val in dic.items(): new_dic[key - minus_value] = val return new_dic# 获取字典的所有键大于0部分def positiveKey(dic): new_dic = {} for key, val in dic.items(): if key > 0: new_dic[key] = val return new_dicA = [16, 18, 20]B = [12, 10, 15]counter = {}# 将B元素值作为键，相同项合并for b, a in zip(B, A): if b not in counter: counter[b] = a else: counter[b] += a# 以2元购买所有所需的糖果total = sum(A) * 2# 以1元购买的糖果数量discount = 0# 找到最大键和最小键while 1: if len(counter) > 1: minb = min(counter.keys()) maxb = max(counter.keys()) # 如果最大键对应的值（即所需购买的糖果数量）小于最小键 if counter[maxb] < minb: tmp = counter[maxb] del counter[maxb] counter = minusKey(counter, tmp) else: # 如果最大键对应的值（即所需购买的糖果数量）大于最小键 counter[maxb] -= minb counter = minusKey(counter, minb) counter = minusKey(counter, counter[0]) for k, v in counter.items(): if k <= 0: discount += v counter = positiveKey(counter) elif len(counter) == 1: # 只剩一个键值对时，折扣数量要求小于所需数量才需要增加discount for k, v in counter.items(): if k < v: discount += (v - k) breakres = total - discountprint(res)
查看2道真题和解析
