【题目来源】
洛谷：P1094 [NOIP 2007 普及组] 纪念品分组 - 洛谷 (luogu.com.cn)
【题目描述】
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
【输入】
共 \(n+2\) 行：
第一行包括一个整数 \(w\)，为每组纪念品价格之和的上限。
第二行为一个整数 \(n\)，表示购来的纪念品的总件数 \(G\)。
第 \(3~n+2\) 行每行包含一个正整数 \(P_i\) 表示所对应纪念品的价格。
【输出】
一个整数，即最少的分组数目。
【输入样例】
100
9
90
20
20
30
50
60
70
80
90
【输出样例】
6
【解题思路】
【算法标签】
《洛谷 P1094 纪念品分组》 #贪心# #排序# #NOIP普及组# #2007#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件
using namespace std;int w, n, l, r, a[30005], ans = 0; // w: 最大承重, n: 物品数量, l/r: 左右指针, a: 物品重量数组, ans: 结果计数器int main()
{// 输入最大承重和物品数量cin >> w >> n;// 输入每个物品的重量for (int i = 1; i <= n; i++) {cin >> a[i];}// 将物品按重量从小到大排序sort(a + 1, a + n + 1);// 初始化双指针l = 1; // 指向最轻的物品r = n; // 指向最重的物品// 使用贪心算法计算最少需要的运输次数while (l <= r) {if (a[l] + a[r] > w) { // 如果最轻和最重的不能一起运输ans++; // 单独运输最重的r--; // 移动右指针} else { // 如果可以一起运输ans++; // 计数一次运输l++; // 移动左指针（最轻的）r--; // 移动右指针（最重的）}}// 输出最少运输次数cout << ans << endl;return 0;
}
【运行结果】
100
9
90
20
20
30
50
60
70
80
90
6