P1094 [NOIP 2007 普及组] 纪念品分组
题目描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
本题为 NOIP 2007 普及组 T2。
输入格式
第一行输入一个整数 w(80≦w≦200) 代表每组纪念品价格之和的上限。
第二行输入一个整数 n(1≦n≦3×104) 代表购来的纪念品的总件数。
此后 n 行,第 i 行输入一个整数 pi(5≦pi≦w) 代表第 i 件纪念品的价格。
输出格式
在一行上输出一个整数,代表最少的分组数目。
测试样例
100
9
90
20
20
30
50
60
70
80
90
6
样例 1 解释
一种最优分组方案为 {90}、{90}、{80,20}、{70,20}、{60,30}、{50},共 6 组。其中价格为 90 的两件纪念品无法与任何其他纪念品配对,而 80 与 20、70 与 20、60 与 30 的价格之和都不超过上限 100。
数据范围与提示
对于 50% 的数据,满足 1≦n≦15。
对于 100% 的数据,满足 1≦n≦3×104,80≦w≦200,5≦pi≦w。