来自Facebook算法比赛的题目（二）

FacebookHackerCup

FacobookHackerCup是facebook下面的一个算法比赛，始于2011年，每年举办一届。来自世界各地的coder都能够参加该项比赛。在前两天，HackCup刚进行完资格赛的选拔。资格赛有三个题目，只要通过其中之一就可以获得晋级。我们来看看资格赛的题目吧。今天先看第二题。

题目

有N个物品，第i个物品的重量为w[i]，现在要将物品分成若干组，需要满足每一组的个数乘以最大的物品重量大于等于50，问最多能分成多少组。

样例输入（不完整）

第一个数T表示样例的数量，每个样例第一个数N表示物品的数量，接下来N个数，表示第i间物品的重量。

样例输出

第1个样例，我们可以分别分成两个（30,1）(30,1)每个的分数都是60，满足条件

第3个样例，我们可以分成(1,3,5,7,9,11)(2,4,6,8,10).第一组66，第二组50

原题

思路

这个题目比较简单，我们先观察一下分数的计算规则，我们会发现，一组的分数只与个数跟最大的物品重量有关系，也就是说同一个分组里面，除了重量最大的，其他的物品都只当做一个权，重量都被浪费，如果我们要获得最大的结果，那么肯定要浪费的越来越少。

我们不难想出这么一个贪心的思路，先把物品按重量排序，然后每次取最大的一个，如果不满足条件，就从小的开始取，直到满足条件为一组。

代码

• 第12行 排序

• 17-19行 如果分数大于等于50，直接加1

• 24-30行 如果分数不够50，那么从小的开始，一个一个加进来。

  总结：

  贪心算法，就是找到合理的策略，然后进行模拟。当然，这个代码写得有点繁琐了，可以写的更好。