法一：题面给出了\(k,2k,3k\)这些数，容易想到调和级数。于是尝试对于每个\(k\)，我们取找出升级的每段（也就是对怪物序列进行划分，每一段的等级相同，相邻两段等级相差一），然后看这篇题解；所以以后遇到处理\(\overset{r}{\underset{i=l}{\sum}}[a_i>x]\)这种式子就可以想根号算法
法二：转换考虑对象。考虑一个怪兽什么时候会被打到。一个感性的想法就是\(k\)越大，需要打的怪兽就越多，于是到同一个怪兽的等级就越低，怪兽就会从逃跑变成应战。于是有一个很自然的想法，设\(f[i]\)表示第\(i\)个怪兽应战的最低的\(k\)。求\(f[i]\)的时候，只需二分\(k\)，并查找\(1\) ~ \(i-1\)中的\(f\leq k\)的个数，设为\(cnt\)，如果\(\lfloor\frac{cnt}{k}\rfloor+1\leq a_i\)，那么这个\(k\)就可以，否则就不行。上述过程可以用树状数组优化，时间复杂度为两个\(\log\)（当然遇到树状数组加二分可以想到树状数组加倍增，将时间复杂度优化为一个\(\log\)）；然而我考试的时候是想到这里的，但是没有敢写，为啥？因为有另一种想法，就是\(k\)越大，应战的怪兽就越多了，可能会抵消\(k\)增大的影响，导致升级还是不会更慢（甚至更快），也就是说没有单调性（从数学表达式\(\lfloor\frac{cnt}{k}\rfloor\)也可以看出来，\(k\)增大，\(cnt\)肯定也增大的），那么上述过程就错了；这个时候，考场就直接写嘛，这代码40行太好写了吧，这场rating纯属白给。重新做的时候想出来了单调性证明方法了。下面给出单调性证明：设\(k_1>k_2\)，那么当我们等级变成\(2\)的时候，肯定是前者所在的怪兽的下标更大，此时我们将所有等级为\(1\)的怪兽移除（相当于这些怪兽没有用了），然后再计算\(k_1,k_2\)两种情况下，我们等级为\(2\)的地方。不难知道，此时对于\(k_1\)，下标更大了，而且由于\(k_1>k_2\)，说明我们对怪兽的需求数量也更大了，于是可以知道升到\(2\)级的坐标肯定会更大。其余情况同理可证
法三：法二给出了单调性证明。现在考虑只求一个怪兽的\(f\)，那么直接二分，并且每次暴力循环，时间复杂度为\(O(n\log n)\)；如果现在要对\(n\)个怪兽求解，时间复杂度就是\(O(n^2\log n)\)；遇到这种“单个二分没问题整个二分就超时”就可以上整体二分了
标签：二分,怪兽,cnt,log,Level,复杂度,Up,等级 From： https://www.cnblogs.com/dingxingdi/p/18366220