纪念品发放问题

新学期到了，校学生会让乐乐负责迎新晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。 输入 多组数据，每组数据共n+2行，第1行包括一个整数w(80<=w<=200)，为每组纪念品价格之和的上限。第2行为一个整数n(1<=n<=30000)，表示购来的纪念品的总件数。第3～n+2行每行包含一个正整数pi(5<=pi<=w)，表示所对应纪念品的价格。输入数据以0结束。 输出 每组数据输出一行，包含一个整数，即最少的分组数目。 样例输入 100 9 90 20 20 30 50 60 70 80 90 0 样例输出 6 ### 纪念品发放问题解析 #### 一、问题背景及目标 在新学期开始之际，校学生会委派乐乐负责迎新晚会的纪念品发放工作。为确保每位参会同学获得的纪念品价值相对均衡，乐乐需将购得的纪念品按价格分组。每组最多只能包含两件纪念品，且每组纪念品的价格总和不得超过一个给定的整数（即每组的价格上限）。为了尽快完成发放工作，乐乐希望分组数量尽可能少。因此，需要编写一个程序来帮助乐乐找到最少分组数目的最优方案。 #### 二、输入输出格式 **输入格式：** - 多组测试数据，每组数据包含以下内容： - 第1行：一个整数 `w` (80 <= w <= 200)，表示每组纪念品价格之和的上限。 - 第2行：一个整数 `n` (1 <= n <= 30000)，表示购得的纪念品总件数。 - 接下来 `n` 行：每行包含一个正整数 `pi` (5 <= pi <= w)，表示对应纪念品的价格。 - 输入数据以 `0` 结束。 **输出格式：** - 对于每组数据，输出一行包含一个整数，即最少的分组数目。 #### 三、示例 **示例输入：** ``` 100 9 90 20 20 30 50 60 70 80 90 0 ``` **示例输出：** ``` 6 ``` #### 四、算法设计说明 为解决上述问题，可以采用以下算法设计思路： 1. **排序：** 对纪念品的价格列表进行排序。 2. **第一次筛选：** 从最大价格开始，寻找与最小价格之和不超过价格上限 `w` 的纪念品，这些纪念品只能单独成组。此步骤完成后，记录下这些单独成组的纪念品数量。 3. **第二次筛选：** - 将剩余纪念品分为两类：大于等于 `w/2` 的纪念品（记为第一类）和小于 `w/2` 的纪念品（记为第二类）。 - 如果第一类纪念品种数多于第二类，则从第一类中最小的纪念品开始，尝试与第二类中最大的纪念品组成一组，只要它们的总和不超过 `w`。 - 如果第二类纪念品种数多于第一类，则从第一类中最大的纪念品开始，尝试与第二类中最小的纪念品组成一组，只要它们的总和不超过 `w`。 4. **剩余纪念品处理：** - 对于未配对的纪念品，尝试两两配对，若无法配对则单独成组。 #### 五、代码实现分析 基于上述算法设计，下面简要介绍关键部分的代码实现逻辑： ```cpp // 假设已读入数据至数组 a[] 和变量 max, total_num sort(a, a + total_num); // 排序 int m = total_num, n = 0; // 初始化变量 while (a[m-1] + a[0] > max) { // 第一次筛选 m--; n++; // 记录单独成组的数量 } int s1 = 0, s2 = 0; // 分类 while (a[m-1] >= max/2) { s1++; m--; } s2 = total_num - n - s1; // 根据 s1 和 s2 的数量差异进行不同处理 if (s1 < s2) { int q = s2, k = 0; while (q >= s2) { if (a[q] + a[k] <= max) { // 更新数量 q--; k++; } else { q--; } } // 进一步处理剩余纪念品 } else { // 类似处理逻辑 } ``` #### 六、总结 通过以上分析可以看出，该问题可以通过排序和分组的方式高效解决。关键在于合理地利用价格上限限制，以及通过分组策略减少最终的分组数量。这种解决方案不仅能够满足题目要求，还能在实际应用中提供有效的参考。