顺丰笔试 2023-9-26

第一题：一个项目组有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 = 100
result = 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_dic


A = [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)
    break
res = total - discount
print(res)