题目描述元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。输入格式输入包含n2行:第1行包括一个整数w为每组纪念品价格之和的上眼 第2行为一个整数n表示购来的纪念品的总件数G第3-n2行每行包含一个正整数Pi (5 Pi w3)w表示所对应纪念品的价格。输出格式输出仅一行包含一个整数 ep最少的分组数目合样例输入100 9 90 20 20 30 50 60 70 80 90样例输出6思路题干要求每组最多 2 件总价≤w希望分组的数目最少。这是典型的贪心算法适用场景最优策略是先排序再用 “双指针” 匹配最小和最大的纪念品尽可能凑成一组从而减少总组数。方案1.先动态内存分配一块连续的内存用于存储数据。2.排序将所有纪念品价格从小到大排序方便后续双指针匹配。3.双指针贪心令左指针*left指向1所分配的内存的首位置最便宜的纪念品、右指针*right指向末位置最贵的纪念品如果*left *right w就让左指针右移、右指针左移否则说明最贵的纪念品过于昂贵故让其自成一组。为什么不让最便宜的自成一组题干要求分组尽可能少最便宜的纪念品可与相对较贵的纪念品组合。每一次成功分组后使得组数。4.思路转代码像动态内存分配、排序算法比较简单核心是双指针贪心的始末怎么实现。1始显然这个算法要多次处理所分配的内存也可以粗略理解成一维数组那么就要使用循环操作。主流的循环有for和while该选择哪一个由于最终要求的就是分的组数也就是循环的执行次数for循环无从下手。那么只有选择while循环了。2末既然已经选择while循环接下来就要思考循环的条件是什么。在上面3内我们规定了左右指针那么当循环执行到最后一组时一定只剩下了一或两个纪念品那么接着会发生什么当处理最后唯一一件纪念品时*left和*right指针是指向同一个位置的假设w100、这个时候剩下的纪念品价值是40运行完之后最后一组组合是{4040}。虽然与现实分组不符{40}但确实是一组此时*left跑到*right右边去了即*left*right。再假设w100最后一件纪念品价值是60这个时候*left *right w那么就会自成一组{40}与实际相同,此时*left也跑到*right右边去了即*left*right。当处理最后两件时此时满足*left *right w随后左右两个指针移动从全局来看就是二者换了个位置此时*left跑到*right右边去了即*left*right。可以看到最后的停止标志就是此时*left跑到*right右边即*left*right所以我要让这个循环执行只要此时*left *right。代码#includeiostream#includealgorithmusing namespace std;int main(){int w, n;cin w n;int* a new int[n];int* left a;int* right a n - 1;for (int i 0; i n; i){cin a[i];}sort(a, a n);int cnt 0;while (left right){if (*left *right w){left;right--;}else{right--;}cnt;}cout cnt;delete[] a;}