题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目
输入描述:
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 pi ( 5 ≤ pi ≤ w ) ，表示所对应纪念品的价格。
输出描述:
包含一个整数，即最少的分组数目。
示例1输入
100 9 90 20 20 30 50 60 70 80 90
示例1输出
6
算法分析:贪心思路,先对所有的纪念品价格进行从小到大排序.然后每次选取最大的和最小的判断是否<=w,如果满足,则说明这两件可以进行分到一组.如果不满足,那么大的只能自己一组(因为和最小的分到一组都不满足条件). 因为中间会有大量元素的删除操作,可以使用STL的vector.
#include<bits/stdc++.h> #include<vector> using namespace std; int w,n,num,cnt; vector<int> V; int main() { cin>>w>>n; for(int i = 0;i < n;i++){ cin>>num; V.push_back(num); } sort(V.begin(),V.end()); int len=V.size(); while(V.size()>1){ if(V[0]+V[V.size()-1]<=w){ V.erase(V.begin()); V.erase(V.end()-1); }else{ V.erase(V.end()-1); } cnt++; } if(V.size()>0){ cnt++; } cout<<cnt<<endl; return 0; }
![【洛谷】P1308 [NOIP2011 普及组] 统计单词数](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_bdac2bf941a740ebaa0f9154a5ed1d20.png?x-oss-process=image/resize,h_160,m_lfit)