csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：纪念品分组

csp信奥赛C高频考点专项训练之贪心算法 --【排序贪心】纪念品分组题目描述元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。输入格式共n 2 n2n2行第一行包括一个整数w ww为每组纪念品价格之和的上限。第二行为一个整数n nn表示购来的纪念品的总件数G GG。第3 ∼ n 2 3\sim n23∼n2行每行包含一个正整数P i P_iPi​表示所对应纪念品的价格。输出格式一个整数即最少的分组数目。输入输出样例 1输入 1100 9 90 20 20 30 50 60 70 80 90输出 16说明/提示50 % 50\%50%的数据满足1 ≤ n ≤ 15 1\le n\le151≤n≤15。100 % 100\%100%的数据满足1 ≤ n ≤ 3 × 10 4 1\le n\le3\times10^41≤n≤3×10480 ≤ w ≤ 200 80\le w\le20080≤w≤2005 ≤ P i ≤ w 5 \le P_i \le w5≤Pi​≤w。AC代码#includebits/stdc.husingnamespacestd;constintN3e410;// 定义足够大的数组大小防止溢出intw,n,cnt0;// w为每组价格上限n为纪念品数量cnt记录最少分组数inta[N];// 存储各纪念品的价格intmain(){cinwn;for(inti1;in;i)cina[i];// 输入纪念品价格sort(a1,an1);// 将价格升序排序便于后续双指针贪心匹配intleft1,rightn;// 双指针初始化分别指向最小和最大元素while(leftright){// 尝试将最大和最小元素配对if(a[left]a[right]w){right--;// 价格超限单独处理当前最大值cnt;// 分组数1}else{left;// 配对成功移动双指针缩小范围right--;cnt;// 分组数1}}// 处理剩余单个元素的情况if(leftright)cnt;coutcnt;return0;}功能分析输入处理与排序首先读入每组价格上限和纪念品总数接着将所有纪念品价格存入数组并升序排序。排序后便于使用双指针策略高效配对。双指针贪心匹配初始化左指针指向最小元素右指针指向最大元素。循环尝试将当前最大元素与最小元素配对若两者之和不超过价格上限则成功配对双指针向中间移动分组数1。若超出上限则单独处理最大元素右指针左移分组数1。处理剩余元素循环结束后若左右指针重合说明剩余一个未处理元素单独成组。该算法时间复杂度为O(n log n)主要由排序步骤决定适用于题目给定的数据规模n ≤ 3×10^4。通过每次尽可能合并大值和小值确保分组数最少符合贪心选择性质。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}