题目描述

小蓝最近正在玩一款 RPG 游戏。

他的角色一共有 $N$ 个可以加攻击力的技能。

其中第 $i$ 个技能首次升级可以提升 $A _ i$ 点攻击力，以后每次升级增加的点数都会减少 $B _ i$。

$\big \lceil {A _ i \over B _ i} \big \rceil$（上取整）次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

输入格式

输入第一行包含两个整数 $N$ 和 $M$。

以下 $N$ 行每行包含两个整数 $A _ i$ 和 $B _ i$。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 $40 \%$ 的评测用例，$1 \le N, M \le 1000$；
对于 $60 \%$ 的评测用例，$1 \le N \le 10 ^ 4$，$1 \le M \le 10 ^ 7$；
对于所有评测用例，$1 \le N \le 10 ^ 5$，$1 \le M \le 2 \times 10 ^ 9$，$1 \le A _ i, B _ i \le 10 ^ 6$。

输入样例：

3 6
10 5
9 2
8 1

输出样例：

47

解题思路

Part 1：观察

我们用贪心容易发现，小蓝升级的攻击力数肯定是尽可能最高的。也就是说，存在一个分界点 $x$，使得小蓝所有升级的攻击力数 $\forall i \in [1, m], \text {up} _ i \ge x$（其中 $\text {up} _ i$ 是第 $i$ 次升级的攻击力数）。又注意到，$1 \le A _ i \le 10 ^ 6$，所以我们可以采取二分答案。

有一个地方需要读者注意：我们可能不会把等于 $x$ 的 $\text {up} _ i$ 全部取走，可能只取一部分。因此我们在二分时只计算严格大于 $x$ 的 $\text {up} _ i$。

Part 2：求和

我们接下来的 $\text {Part 3}$ 中会用到这个函数。对于一个末项为 $r$，项数为 $n$，公差为 $t$ 的等差数列，我们考虑先算出它的首项 $l = r - t(n - 1)$，再用等差数列求和公式 $S = \frac {(l + r)n} 2$ 求出和。

long long sum (int r, int n, int t) // 求和函数
{
    int l = r - t * (n - 1);
    return (long long) (l + r) * n >> 1;
}

Part 3：二分

我们二分这个 $x$（见 $\text {Part 1}$），二分域 $[0, 10 ^ 6]$（为什么左端点是 $0$ 而不是 $1$ 后面再讲），把 严格大于 $\mathbf x$ 的升级都计算上。$x = mid$ 时的升级次数和为 $res = \sum {} _ {A _ i > x} \big \lceil {A _ i - x \over B _ i} \big \rceil$。check 函数判断 $res$ 是否 $\le m$ 即可。

具体来说，我们找到所有满足 $A _ i > x$ 的 $i$，将 $res$ 累加上 $\big \lceil {A _ i - x \over B _ i} \big \rceil$ 即第 $i$ 个技能的使用次数（从题意中的 $\big \lceil {A _ i \over B _ i} \big \rceil$ 转化而来）；最后判断如果 $res \le m$ 即是合法，否则不合法。

$\textbf {check}$ 函数：

bool check (int x)
{
    long long res = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] > x) // 前提条件
        {
            res += ceil ((double) (a[i] - x) / b[i]);
            // 累计第 i 个技能发动的次数
        }
    }
    return res <= m; // 判断是否合法
}

Part 4：求解

二分后我们得到一个 $l$ 使得所有 $\text {up} _ i$ 都 $\ge l$。我们先按二分 check 函数的方法统计出一个 严格大于 $\mathbf x$ 的升级次数，同时运用 $\text {Part 2}$ 提到的求和公式计算出总升级攻击数之和：

for (int i = 1; i <= n; i ++)
{
    if (a[i] > l) // 前提条件
    {
        now = ceil ((double) (a[i] - l) / b[i]), cnt += now;
        // now 是第 i 个技能发动的次数，cnt 则是总共升级了多少次
        ans += sum (a[i], now, b[i]);
        // 总升级攻击力累加上右端点为 a[i]，项数为 now，公差为 b[i] 的等差数列和
    }
}

最后还要加上等于 $l$ 的技能发动。由于我们已经算过 $> l$ 的技能发动一共有 $cnt$ 次，而我们希望取 $m$ 次技能发动，因此我们应该取 $m - cnt$ 次的技能发动。所以最终答案为 $ans + (m - cnt)l$。

如果有些奇奇怪怪的数据（确实有）的 $m$ 大于了有效的发动次数，即有些发动是无效、不增加攻击力的，$l$ 就会等于 $0$。这时程序仍可以给出正确答案。

还是那句话：不开 long long 见祖宗。

AC Code

#include <iostream>
#include <cmath>
#define N 100005
using namespace std;

int n, m, l = 0, r = 1e6, mid, now, cnt, a[N], b[N];
long long ans;

long long sum (int r, int n, int t) // 求和
{
    int l = r - t * (n - 1);
    return (long long) (l + r) * n >> 1;
}

bool check (int x)
{
    long long res = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] > x) // 前提条件
        {
            res += ceil ((double) (a[i] - x) / b[i]);
            // 累计第 i 个技能发动的次数
        }
    }
    return res <= m; // 判断是否合法
}

int main ()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
    }
    while (l < r) // 二分
    {
        mid = l + r >> 1;
        if (check (mid)) // 如果 x = mid 合法
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] > l) // 前提条件
        {
            now = ceil ((double) (a[i] - l) / b[i]), cnt += now;
            // now 是第 i 个技能发动的次数，cnt 则是总共升级了多少次
            ans += sum (a[i], now, b[i]);
            // 总升级攻击力累加上右端点为 a[i]，项数为 now，公差为 b[i] 的等差数列和
        }
    }
    cout << ans + (long long) l * (m - cnt); // 答案还要记得加上那些等于 l 的攻击力增加
    return 0;
}

感谢观看！

由于作者太菜，有疑问的可以在评论区进行提问。

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$