LG#P1094. [NOIP 2007 普及组] 纪念品分组

[NOIP 2007 普及组] 纪念品分组

P1094 [NOIP 2007 普及组] 纪念品分组

题目描述

\hspace{15pt}元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

\hspace{15pt}你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

\hspace{15pt}本题为 NOIP 2007 普及组 T2。

输入格式

\hspace{15pt}第一行输入一个整数 w(80≦w≦200)w \left(80 \leqq w \leqq 200\right) 代表每组纪念品价格之和的上限。

\hspace{15pt}第二行输入一个整数 n(1≦n≦3×104)n \left(1 \leqq n \leqq 3 \times 10^4\right) 代表购来的纪念品的总件数。

\hspace{15pt}此后 nn 行,第 ii 行输入一个整数 pi(5≦pi≦w)p_i \left(5 \leqq p_i \leqq w\right) 代表第 ii 件纪念品的价格。

输出格式

\hspace{15pt}在一行上输出一个整数,代表最少的分组数目。

测试样例

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

6

样例 1 解释

\hspace{15pt}一种最优分组方案为 {90}\{90\}、{90}\{90\}、{80,20}\{80, 20\}、{70,20}\{70, 20\}、{60,30}\{60, 30\}、{50}\{50\},共 66 组。其中价格为 9090 的两件纪念品无法与任何其他纪念品配对,而 8080 与 2020、7070 与 2020、6060 与 3030 的价格之和都不超过上限 100100。

数据范围与提示

\hspace{15pt}对于 50%50\% 的数据,满足 1≦n≦151 \leqq n \leqq 15。

\hspace{15pt}对于 100%100\% 的数据,满足 1≦n≦3×1041 \leqq n \leqq 3 \times 10^4,80≦w≦20080 \leqq w \leqq 200,5≦pi≦w5 \leqq p_i \leqq w。