技能升级

题目

解题方法

整体来说，我们其实就是求出所有技能包括按了之后的攻击力，然后求出前M大的技能，最后就是答案。有以下几种方法：

优先队列

我们可以先把所有攻击力进行排序，从大到小的顺序。每当我们取出最大的技能之后，将这个技能减少b，在添加到队列当中。这样选出M个就是答案。但是这样会超时，最后的时间复杂度是MlogM这样一定会超时。

二分

在这里我们需要考虑是不是可以直接找到M这个位置或者找到这个x值的技能？使用二分？

求出x值

我们首先考虑一下x的值是否有二段性质？

1. 如果当前值 > x，那么前面的数字一定是 > M
2. 反之，前面的数字一定是 <= M

判断前面的和

二分的过程是logM肯定满足要求，但是我们如何根据x判断前面有多少数字呢？

我们每一个技能和他按下 直到没有攻击力组成的序列是一个等差序列，其实等价于 这个等差序列中 小于x的数字有多少个？我们可以使用(a - x) / d下取整求的。遍历所有技能就可以求出来，所以求出来x这个值就是NlogM的时间复杂度。

既然我们求出来了x，如何求出来前面的所有和？很简单，我们等差序列 首项a 公差d 我们可以知道大于x的项数，那么我们可以O(1)的时间复杂度求出和。最后只要减去x中超过M的和就好了。]