关于此题贪心的补充证明
查看原帖
关于此题贪心的补充证明
432566
carefree_Zhuang楼主2024/1/20 12:12

正确的贪心:

找到最小的元素 axa_x ,若找到第一个不小于 l−axl-a_x 的元素 aya_y ,去除这两个元素,ans++ans++;若没找到,跳到 axa_x 元素大小上的后继 (可以理解成将集合当成序列,按大小排,遍历)

证明:

分类:

1、最优匹配中包含 axa_x

则应该选择 aya_y,因为选择小于它的元素都不满足条件。选择大于它的元素的情况,选择 aya_y 对其是具有决策包容性的

2、最优匹配中不包含 axa_x

则最优排列中必然包含 aya_y,否则还有未统计的匹配对 (ax,ay)(a_x,a_y).设 aya_y 与 aza_z 匹配,显然 az≥axa_z \geq a_x.那么这个匹配可能不是最优,或与选axa_x等效。

所以,以上贪心方法是正确的

没有讲做题思路,应该不算讨论区题解

2024/1/20 12:12
加载中...