【华为机试】2023年真题B卷（python）-计算礼品发放的最小分组数目

一、题目

题目描述：

又到了一年的末尾，项目组让小明负责新年晚会的小礼品发放工作。
为使得参加晚会的同时所获得的小礼品价值相对平衡，需要把小礼品根据价格进行分组，但每组最多只能包括两件小礼品，并且每个分组的价格总和不能超过一个价格上限。
为了保证发放小礼品的效率，小明需要找到分组数目最少的方案。
你的任务是写一个程序，找出分组数最少的分组方案，并输出最少的分组数目。

二、输入输出

输入描述：
第一行数据为分组礼品价格之和的上限
第二行数据为每个小礼品的价格，按照空格隔开，每个礼品价格不超过分组价格和的上限
输出描述：
输出最小分组数量

三、示例

示例1：
输入：
5
1 2 5
输出：
2

四、解题思路

1. 首先，我们需要将输入的小礼品价格列表按照从小到大的顺序进行排序，这样可以方便我们进行分组。
2. 创建一个变量count，用于记录分组的数量。
3. 创建一个变量total，用于记录当前分组的价格总和。
4. 遍历排序后的小礼品价格列表，对于每个小礼品的价格price，进行以下操作：
   • 如果total加上price小于等于分组价格上限，说明当前分组还可以加入一个小礼品，将total更新为total加上price。
   • 否则，当前分组已满，需要新建一个分组，将count加1，并将total更新为price。
5. 遍历完所有小礼品后，返回count作为最小分组数量。

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-计算礼品发放的最小分组数目.py
@Time    :   2023/12/29 22:38:42
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def find_min_group_count(limit, prices):
    prices.sort()  # 对小礼品价格列表进行排序
    count = 0  # 分组数量
    total = 0  # 当前分组的价格总和

    for price in prices:
        if total + price <= limit:
            total += price
        else:
            count += 1
            total = price

    count += 1  # 最后一个分组可能未满，需要加1

    return count


limit = int(input())
prices = [int(i) for i in input().split()]
result = find_min_group_count(limit, prices)
print(result)