蓝桥532.纪念品分组 ​

题目 ​

题目描述 ​

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述 ​

第 1 行包括一个整数 $w$（$80\le w\le 200$），为每组纪念品价格之和的上限。 第 2 行为一个整数 $n$（$1\le n\le 30000$），表示购来的纪念品的总件数。 第 3 ~ $n+2$ 行每行包含一个正整数 $p_i$（$5\le p_i\le w$），表示所对应纪念品的价格。

输出描述 ​

输出一行，包含一个整数，即最少的分组数目。

示例 ​

输入：

100
9
90
20
20
30
50
60
70
80
90

输出：

6

题解 ​

为了最小化分组数目，采用贪心思想，将纪念品按价格从小到大排序，然后使用双指针从两端向中间配对：

1. 排序：将所有纪念品的价格按升序排列。
2. 双指针：设置两个指针，一个指向最小价格（left），一个指向最大价格（right）。
3. 配对：尝试将最小价格和最大价格的纪念品配对。如果它们的和不超过 $w$，则形成一个组，同时移动两个指针；否则，最大价格的纪念品只能单独成组，移动右指针。
4. 计数：每形成一个组（无论是单个还是两个纪念品），计数器加一。

w = int(input())
n = int(input())
prices = [int(input()) for _ in range(n)]
prices.sort()
left = 0
right = n - 1
groups = 0
while left <= right:
    # 如果最小和最大的价格之和不超过w，可以组成一组
    if prices[left] + prices[right] <= w:
        groups += 1
        left += 1
        right -= 1
    else:
        # 如果无法组成一组，最大的价格单独成组
        groups += 1
        right -= 1
print(groups)

1. 这个算法的时间复杂度为 $O(n\log n)$，受限于排序操作。