正确的贪心:
找到最小的元素 ax ,若找到第一个不小于 l−ax 的元素 ay ,去除这两个元素,ans++;若没找到,跳到 ax 元素大小上的后继
(可以理解成将集合当成序列,按大小排,遍历)
证明:
分类:
1、最优匹配中包含 ax
则应该选择 ay,因为选择小于它的元素都不满足条件。选择大于它的元素的情况,选择 ay 对其是具有决策包容性的
2、最优匹配中不包含 ax
则最优排列中必然包含 ay,否则还有未统计的匹配对 (ax,ay).设 ay 与 az 匹配,显然 az≥ax.那么这个匹配可能不是最优,或与选ax等效。
所以,以上贪心方法是正确的
没有讲做题思路,应该不算讨论区题解