题目描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入输出格式
输入格式:
共n+2行:
第1行包括一个整数w,为每组纪念品价格之和的上上限。
第2行为一个整数n,表示购来的纪念品的总件数G。
第3至n+2行每行包含一个正整数P_i(5 \le P_i \le w)表示所对应纪念品的价格。
输出格式:
一个整数,即最少的分组数目。
输入输出样例
输入样例#1:
100 9 90 20 20 30 50 60 70 80 90
输出样例#1:
6
题解
由题意可知,一共有n件物品,易推断出当对w的利用率最大时,分组最少。
而当最大物品和最小物品放在一起时对w的利用率最大。
#include<bits/stdc++.h> using namespace std; int main() { int w,g,p[30001],gc=0,i=0;//gc用来计数 cin>>w>>g; int t=g-1;//因为是从0开始计数,所以末尾要减一 for(;i<g;i++) { cin>>p[i]; } sort(p,p+g);//排序 i=0;//重置i while(t>i) { if(p[i]+p[t]>w) gc++,t--;//如果此时装不下则说明p[t]需独占一个空间 if(p[i]+p[t]<=w) gc++,t--,i++;//装得下 } if(t==i) gc++;//其他都装完了,剩下一个,需独占 cout<<gc; return 0; }