想法

读完题就发现有一个贪心地方，每次升级小蓝必然选择当前收益最高的，也就是增加攻击力最多的技能，因此只需要枚举 $m$ 此，用堆维护收益最高的技能就可以成功地 TLE 本题。

时间复杂度：$O(m\log n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;

priority_queue<PII> heap;

int a[N], b[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        heap.push({a[i], i});
    }
    int ans = 0;
    for(int i = 1; i <= m; i ++)
    {
        ans += heap.top().x;
        int id = heap.top().y;
        heap.pop();
        a[id] -= b[id];
        heap.push({a[id], id});
    }
    cout << ans << endl;
    return 0;
}

优化

接下来考虑优化。

沿着贪心的思路往下走，如果每次都选择收益最大的技能 $i$，我们将每次选择得到的攻击力 排成一个序列，这个序列一定是单调递减的。

以样例为例，最后选取技能所组成的序列为：

$$10, 9, 8, 7, 7, 6$$

通过序列的单调性萌生了一个二分答案的想法——二分最后一次选择得到的攻击力 $l$ 。

因此所有 $> l$ 的攻击力都是可以被选择的，而 $=l$ 的攻击力则需要看情况，check 函数自然就是判断选择次数是否 $\geq m$。

此时我们需要一个快速得到选择次数的方法，可以简单推导一下：

假设对于技能 $i$，我们选择了 $t$ 次，则有：
$$\begin{aligned} a_i - b_i \times (t - 1)&\geq l\\\ a_i - l &\geq b_i \times (t - 1)\\\ \dfrac{a_i - l}{b_i} &\geq t - 1\\\ \lfloor\dfrac{a_i - l}{b_i}\rfloor &= t-1 \\\ t &= \lfloor\dfrac{a_i - l}{b_i}\rfloor + 1\\\ \end{aligned}$$

由此可在 $O(1)$ 时间内套公式求出选择次数，有一些细节在代码中。

这是 bool check() 函数与二分的实现：

bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= n; i ++)
        if(a[i] >= x) // 如果 < x 则可能会出现负数
        sum += (a[i] - x) / b[i] + 1;

    return sum >= m;
}

int l = 0, r = 1e6 + 5;
while(l <= r)
{
    int mid = l + r >> 1;
    if(check(mid)) l = mid + 1;
    else r = mid - 1;
}
l --; // 这个二分板子需要 l--

现在我们已经在 $O(n\log n)$ 时间内求出了最后一次（也是最小）的攻击力，只需要根据这个得到最终的答案就好了。

假设对于技能 $i$，我们选择了 $t$ 次，我们同样可以在 $O(1)$ 的时间内找出技能 $i$ 对答案的总贡献

左为技能 $i$ 对答案的总贡献，右为选择次数 $t$。

$$\left\{\begin{matrix} a& &1 \\ 2a - b& &2 \\ 3a - 3b& &3\\ 4a - 6b& &4\\ 5a - 10b& &5\\ \dots \\ta - \dfrac{t(t -1)}2b && t\end{matrix}\right.$$

得到一个快速求技能 $i$ 对答案的总贡献的公式。

for(int i = 1; i <= n; i ++)
{
    int t = ((a[i] - l) / b[i] + 1); // 次数公式
    if(t <= 0 || a[i] < l) continue; // 防止负数

    if(a[i] - (t - 1) * b[i] == l) // 特殊处理刚好等于最后一次攻击力的情况
        t --;

    ans += t * a[i] - (t * (t - 1) / 2 * b[i]); // 贡献公式
    m -= t; // 剩余可用次数减去此处已用次数
}

答案部分需要加上 $m\times l$，表示等于最后一次选择攻击力 $l$ 的技能的贡献

完整代码

时间复杂度：$O(n\log n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];
int n, m;

bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= n; i ++)
        if(a[i] >= x)
        sum += (a[i] - x) / b[i] + 1;

    return sum >= m;
}

signed main()
{
    int tot = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        tot += (a[i] - 1) / b[i] + 1;
    }
    m = min(m, tot); // 防止可选择次数 > 能选择的次数出现负数
    int ans = 0;

    int l = 0, r = 1e6 + 5;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    l --;

    for(int i = 1; i <= n; i ++)
    {
        int t = ((a[i] - l) / b[i] + 1);
        if(t <= 0 || a[i] < l) continue;

        if(a[i] - (t - 1) * b[i] == l)
            t --;

        ans += t * a[i] - (t * (t - 1) / 2 * b[i]);
        m -= t;
    }
    cout << ans + m * l << endl;
    return 0;
}

感谢 atzy 大佬指出的错误！