CF1601D

神奇贪心题

贪心一直是我的最大短板之一

题解

将所有二元组按照 (max(a,s)) 排序,然后从前往后扫一遍即可得出答案。

证明:

所有的二元组可以被分为两类

(1:aleq s)(2:a leq s)

对于第一类二元组,我们最差也可以全部选择,在此基础上我们只要再选若干个第二类二元组即可。

排序之后对于二元组 ((a_i,s_i))

若该二元组属于第一类,我们可以保证它前面所选择的二元组一定不会对自己造成影响。

若该二元组属于第二类,因为不会影响后面的二元组所以能选就选。

这样可以保证最大个数

博客园这个代码渲染做的也太拉了吧

代码

原文地址:https://www.cnblogs.com/-Iris-/p/15480990.html