问题 1352. -- 小型飞船

1352: 小型飞船

时间限制: 1 Sec  内存限制: 128 MB
提交: 169  解决: 78
[提交][状态][讨论版]

题目描述

有一批太空物资需要用小型飞船运送，每个小型飞船每次最多只能运送总重量不超过w的两件物品。为了节约运费，将这批物资经合理组合后装船后一次性运送，共需多少小型飞船？

输入

共二行
第一行共有2个正整数：w,n ( 10 <= w <= 200 )
第二行共有n个不超过w的正整数：依次表示n件物品的重量，相邻两数间用一个空格隔开

输出

只有一行且只有一个正整数：最少的小型飞船数目

样例输入

100 9
90 20 20 30 50 60 70 80 90

样例输出

6

提示


【样例说明】

这6艘小型飞船的载重量可以是：90，90，80+20，70+30，60+20，50。



【数据规模】     

50% 的数据:  1 <= n <= 100

80% 的数据:  1 <= n <= 1 0000

100% 的数据:  1 <= n <= 30 000

来源

贪心算法

[提交][状态]