Skip to content

Latest commit

 

History

History

2557.Maximum-Number-of-Integers-to-Choose-From-a-Range-II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2557.Maximum-Number-of-Integers-to-Choose-From-a-Range-II

我们猜测能够取到的最大的数值为m。只要确定了m,我们可以计算出[1,m]之间能够取到的元素的和sum是多少。如果sum大于maxSum,那么我们就猜测更小的m,否则就猜更大的数。

如何计算sum呢?首先就是计算1到m的等差数列之和。然后在排序后的banned里用upper_bound定位第一个大于m的位置。如果这个位置的index是t,那么就意味着banned里面有t个元素小于等于m,那么我们就需要将banned的前t个元素的和减去。

我们二分搜索求出m之后,还需要减去t,才是最后的答案。

注意,二分搜索的收敛值m有可能是banned中的元素,但是对于本题的解没有影响。因为本题的答案是最终取多少个元素。m终究是会被减去的。