「PA 2019」Szprotki i szczupaki

较为简单的数据结构题。
考虑如下贪心过程：

ts=s
st=初始鱼的集合 
ans=0
while(1){
	p=st的小于s的最大数
	如果st没有小于s的数 
		break
	ans+=1
	ts+=p
}

正确性是显然的。
然而这样子做时间复杂度并不正确。
如果鱼的重量为\(100000,1,1,1,(100000)\)个\(1\)那么就会被卡。
显然可以使用线段树优化。
设在集合内的第一个大于\(ts\)的值为\(y\)，则我们可以在线段树上二分加速寻找\(st\)的小于\(s\)的最大数的过程，具体可以看代码。
这样子看似还是很暴力。
然而每次线段树二分一次后，我们的值都会大于原值的两倍，所以时间复杂度为\(O(n\log_2n\log_2V)\)

「PA 2019」Szprotki i szczupaki

原文：https://www.cnblogs.com/ctmlpfs/p/14157999.html