• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1529B Sifid and Strange Subsequences

开发技术 开发技术 3天前 3次浏览

(text{Description})

给定长度为 (n) 的序列 (a),求一个子集 (S),使得 (forall i,jin S,|a_i-a_j|ge text{MAX}),其中 (text{MAX}=max_{iin S} a_i),最大化 (|S|)

(text{Solution})

首先对于所有的非正数,都是可以添加进来的。因为添加所有的非正数,(text{MAX}le0),而一个数的绝对值 (ge 0),所以一定是满足条件的。

而对于正数,有如下两个结论:

  1. 最多只能添加一个正数。

(text{proof:}) 考虑反证法,设选择了 (x,y),假设 $0lt xle y $,则有 (y-x lt y),与条件相悖,故原命题成立。

  1. 如果能添加正数,添加的正数一定是最小的正数。

考虑将所有负数想象成数轴上的点,那么添加正数等同于询问是否有两个点的距离小于这个正数,如果有很显然不成立。那么如果连最小的正数都不能满足,之后的正数一定不能满足这个条件。

而如何检验一个正数是否能加进来呢?

其实方法已经在结论 (2) 的证明中提到了,我们将所有数排序,看是否有两个数之间的差小于该正数即可。

时间复杂度:(Theta(nlog n))排序的复杂度)。

代码不难写,就不放了。


程序员灯塔
转载请注明原文链接:CF1529B Sifid and Strange Subsequences
喜欢 (0)