题目描述
小蓝最近正在玩一款 RPG 游戏。
他的角色一共有 N 个可以加攻击力的技能。
其中第 i 个技能首次升级可以提升 Ai 点攻击力,以后每次升级增加的点数都会减少 Bi。
⌈AiBi⌉(上取整)次之后,再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能,他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力?
输入格式
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40% 的评测用例,1≤N,M≤1000;
对于 60% 的评测用例,1≤N≤104,1≤M≤107;
对于所有评测用例,1≤N≤105,1≤M≤2×109,1≤Ai,Bi≤106。
样例
example input
3 6
10 5
9 2
8 1
example output
47
算法1
Binary Search O(nlog(n))
For all cases, $1 \leq N \leq 10^5, 1 \leq M \leq 2 \times 10^9, 1 \leq A_i, B_i \leq 10^6$, so the time complexity is constrained in O(nlog(n))
. The way to solve the problem is to find a lower bound which for any $i^{th}$ skill that is upgraded, its next upgradeable attack damage a[i] is greater than or equal to the lower bound by using a binary search while the sum of the times skills are updated is less than or equal to m
. If there the sum is less than m
, all remaining upgrades m - cnt
can be done with upgradeable attack damage a[i]
being equal to the lower bound (if not, we can always find an even lower bound than the current lower bound, such that the new lower bound satisfy the condition stated above).
One thing to notice is that the available times of upgrades are (a[i] - x) / b[i]
and then take the ceiling value since the first upgrade does not suffer from b[i]
points loss, this can be done using (a[i] - x + b[i] - 1) / b[i]
.
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
bool check(int x) {
LL cnt = 0;
for (int i = 0; i < n; i ++ ) cnt += a[i] > x ? (a[i] - x + b[i] - 1) / b[i] : 0;
return cnt <= m;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i], &b[i]);
int l = 0, r = 1e6;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
LL res = 0, cnt = 0, temp = 0;
for (int i = 0; i < n; i ++ ) {
if (a[i] > l) {
temp = (a[i] - l + b[i] - 1) / b[i];
cnt += temp;
res += a[i] * temp - temp * (temp - 1) / 2 * b[i];
}
}
res += (LL)(m - cnt) * l;
cout << res << endl;
}