CF1098D

题意

洛谷

做法

排序(a_1le a_2le ...le a_{n-1}le a_n)
定义1：(a_i>2sumlimits_{j<i}a_j)，则称鱼(i)是肥鱼

令(t)为肥鱼个数

结论1：(dangerle n-t)

证明：
考虑每条肥鱼单独与一个集合合并的贡献即可，即便产生了贡献，也是破坏贡献持平的

结论2：在每一时刻，两个重量最小的鱼争斗

证明：
如果a与b不危险，则b没有吃过其他鱼：假设吃过(b=c+d(cle d)Longrightarrow dge b/2>a)，根据归纳，(a)和(c)之前争斗过

结论3：(danger=n-t)

证明：
考虑对个数归纳，(a_1+a_2>a_k,a_1+a_2le a_{k+1})，则将((a_1+a_2))插到(k,k+1)间
由于(a_i<(a_1+a_2)(iin[3,k]))，则前面(a_i<2(sumlimits_{j=1}^{i-1}a_j)~or~a_ige 2(sumlimits_{j=1}^{i-1}a_j))依然满足(a_i<2(sumlimits_{j=3}^{i-1}a_j)~or~a_ige 2(sumlimits_{j=3}^{i-1}a_j))，而(i>k)，显然不会变化。即所有是否是肥鱼的属性都不会变化。而(a_3)不是肥鱼也转去((a+b))不是肥鱼了。
根据归纳假设，依然满足：(danger=n-t)。

结论4：将值域划分为([2^0,2^1),[2^1,2^2)...,[2^{30},2^{31})...)，每个区间最多只有一条肥鱼，且若有，则必定是区间最小的

根据结论4，随便搞即可

题外话

结论证明的细节较多，可能有写挂的地方，若有请提醒一下