题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入
共 n+2 行：
第一行包括一个整数 w，为每组纪念品价格之和的上限。
第二行为一个整数 n，表示购来的纪念品的总件数 G。
第 3∼n+2 行每行包含一个正整数 Pi 表示所对应纪念品的价格。
输出
一个整数，即最少的分组数目。
样例
输入
100
9
90
20
20
30
50
60
70
80
90
输出
6
说明
数据范围
50% 的数据满足：1≤n≤15。
100% 的数据满足：1≤n≤3×10^4 ，80≤w≤200，5≤Pi ≤w。
分析
根据题目描述，我们需要找到购买的纪念品的最少分组数。每组纪念品的价格之和不能超过给定的上限。
我们可以使用贪心算法来解决这个问题。首先，将纪念品的价格进行排序。然后，使用双指针的方法，从最小的价格和最大的价格开始，依次匹配纪念品，直到两个指针相遇。在匹配的过程中，如果两个纪念品的价格之和小于等于上限，则将它们分为一组。否则，将较大价格的纪念品单独分为一组。
代码
下面是相应的C++代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int w, n;cin >> w >> n;vector<int> prices(n);for (int i = 0; i < n; i++) {cin >> prices[i];}sort(prices.begin(), prices.end());int left = 0;int right = n - 1;int count = 0;while (left <= right) {if (prices[left] + prices[right] <= w) {left++;right--;} else {right--;}count++;}cout << count << endl;return 0;
}
在代码中，我们首先读取输入的上限 w 和纪念品总数 n，并创建一个大小为 n 的数组 prices 来存储每个纪念品的价格。
接下来，我们对 prices 数组进行排序，以便从最小的价格开始匹配。
然后，我们使用双指针的方法，将一个指针 left 指向最小的价格，将一个指针 right 指向最大的价格。在匹配的过程中，如果两个纪念品的价格之和小于等于上限 w，则将它们分为一组，并将 left 指针右移一位，将 right 指针左移一位。否则，将较大价格的纪念品单独分为一组，并将 right 指针左移一位。
最后，输出分组数 count。
