【洛谷贪心算法题】P1094纪念品分组

该题运用贪心算法，核心思想是在每次分组时，尽可能让价格较小和较大的纪念品组合在一起，以达到最少分组的目的。

【算法思路】

1. 输入处理：首先读取纪念品的数量n和价格上限w，然后依次读取每件纪念品的价格，并将其存储在容器vector中

2. 排序：使用 sort 函数对纪念品的价格进行从小到大的排序。排序的目的是方便后续使用双指针法，能快速找到价格最小和最大的纪念品。

3. 双指针初始化：初始化两个指针 left 和 right，分别指向价格最小和最大的纪念品。同时，初始化分组数量 groups 为 0。

4. 分组过程：
   ◦ 当 left 小于等于 right 时，进入循环：
   ◦ 如果 left 等于 right，说明只剩下一个纪念品，将分组数量加 1 并跳出循环。
   ◦ 如果价格最小和最大的纪念品价格之和不超过价格上限 w ，则将它们分为一组，left 指针右移一位，right 指针左移一位，分组数量加 1。
   ◦ 如果价格最小和最大的纪念品价格之和超过价格上限 w ，则将价格最大的纪念品单独分为一组，right 指针左移一位，分组数量加 1。

5. 输出结果：循环结束后，输出分组的数量。

【代码示例】

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int w, n;// 读取每组纪念品价格上限 w 和纪念品数量 ncin >> w;cin >> n;// 使用 n 来初始化 vector 的大小vector<int> P(n);// 读取每个纪念品的价格for (int i = 0; i < n; i++) {cin >> P[i];}// 对纪念品价格从小到大排序sort(P.begin(), P.end());// 双指针法分组int left = 0;int right = n - 1;// 初始化分组数量为 0int groupCount = 0;while (left <= right) {if (left == right) {// 若只剩一个纪念品，单独成一组groupCount += 1;break;}if (P[left] + P[right] <= w) {// 若最小和最大价格的纪念品能分在一组groupCount += 1;left += 1;right -= 1;} else {// 若不能，最大价格的纪念品单独成一组right -= 1;groupCount += 1;}}// 输出最少的分组数量cout << groupCount << endl;return 0;
}

注意：

①双指针一般是整数类型的索引，而非指针类型

②使用 n 来初始化 vector 的大小

③将groupCount初始化为0，避免未定义行为