华为OD机试真题B卷 Java 实现【计算礼品发放的最小分组数目】，附详细解题思路

一、题目描述

又到了一年的末尾，项目组让小明负责新年晚会的小礼品发放工作。

为使得参加晚会的同时所获得的小礼品价值相对平衡，需要把小礼品根据价格进行分组，但每组最多只能包括两件小礼品，并且每个分组的价格总和不能超过一个价格上限。

为了保证发放小礼品的效率，小明需要找到分组数目最少的方案。

你的任务是写一个程序，找出分组数最少的分组方案，并输出最少的分组数目。

二、输入描述

第一行数据为分组礼品价格之和的上限

第二行数据为每个小礼品的价格，按照空格隔开，每个礼品价格不超过分组价格和的上限。

10
5 5 10 2 7

三、输出描述

输出最小分组数量。

3

四、解题思路

1. 从输入中读取分组礼品价格之和的上限max；
2. 从输入中读取每个小礼品的价格，并将其存储在数组arr中；
3. 对数组arr进行排序，以便从最小的价格开始进行分组；
4. 初始化变量num为0，表示分组数目；
5. 使用双指针法，一个指针i指向数组的起始位置，一个指针j指向数组的末尾位置；
6. 当j大于等于i时，进行以下判断：
   • 如果i和j指向同一个位置，表示剩下最后一个礼品，将其视为一个独立的分组，将nu