洛谷：P1094：纪念品分组

题目

P1094：纪念品分组

分析

先列出样例数据方便后续讨论。

100 - 最高100块
9 - 9个纪念品
90 - 价值90
20 - 价值20
20 
30 
50 
60 
70 
80 
90

这道题目不难，贪心策略也很简单：

1. 最难分组的，是价值高的，所以要优先考虑。比如在样例数据中。90元的纪念品无法和别的配对，只能单独一组。
2. 但80的纪念品就可以和20分组。
3. 重复上述过程，直到没有纪念品或者只有一个纪念品。
4. 可以得到6组：
   • 第1组: [90] (单独一组，价值: 90)
   • 第2组: [90] (单独一组，价值: 90)
   • 第3组: [20, 80] (配对一组，价值和: 100)
   • 第4组: [20, 70] (配对一组，价值和: 90)
   • 第5组: [30, 60] (配对一组，价值和: 90)
   • 第6组: [50] (单独一组，价值: 50)

自然地，我们需要排序。另外，这种一头一尾碰头的题目，自然用双指针是最好的。

答案

思考

这道题目不难，但因为在贪心中附加了双指针，所以值得一提。