观察水槽中小球总数的规律可知 Ti−Ti−1=i
因此我们可以轻易得出 Ti=1+2+⋯+i
又由于相邻水槽液面以上的可见小球数之差可确定水槽位置,进而液体深度为 Tb−a−b
时间复杂度为 O(b−a)
有一排深度充足的水槽,水槽从左到右编号为 1,2,3,…。初始时第 i 个水槽中堆叠着 2i(i+1) 个小球,相邻水槽之间的水平间隔为 1,且每个水槽底部高度相同。
现在,水槽群被注入了未知深度的清澈液体,液体表面保持水平。已知在液体表面以上,某两个相邻水槽 k 和 k+1 中可见的小球数量分别为 a 和 b。
请你根据这两个数字计算液体的深度(即每个水槽中被液体淹没的小球数量)。题目保证给定的 a,b 一定对应某个水槽 k,且答案存在且唯一。
约束条件:输入的两个整数满足 1≤a<b≤5×105。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.