做了才知道为什么NowOrNever交那么多次都没过……
首先应该要想到的做法是给每个楼之间的区间分配飞多少层楼的高度。
然后很直接的想法就是每次取涨一层楼代价最小的那个区间来加一的高度，直到这个涨的代价大于1.0/w，或者涨满L这么高。
但是L有10^9，这样做肯定是要TLE的。那么我们可以二分这个+1的代价，然后贪心地去算，然后判断楼层是否超过L就可以了。
不过我的做法更暴力一点，先直接按连续的去做了，差分变成求导，求导以后不难看出这个导数是单调递增的，由于函数是连续的，可以避免很多取整、讨论。于是通过实数的模型可以得到每个区间占用楼层的近似初值。有了这个近似初值，就可以用上面最直接的那个想法通过这道题目。不难证明复杂度是 n lg n的。
留下评论