解题思路: 简化攻击力增加量的计算过程,确保每次升级后都按等差数列求和来计算总增加攻击力。
参考代码:
#include <stdio.h>
#include <limits.h>
#define max 100010
int n, m;
long long att = 0; // att:攻击力
int a[max], b[max]; // cnt:升级次数
// 检查有没有可能第m次增加攻击力大于x
int check(int x) {
long long cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) {
cnt += (a[i] - x) / b[i] + 1; // a[i]到x要经过cnt次
if (cnt >= m) // 若m次攻击力>=x,则有可能,返回true
return 1;
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
int tcnt = 0;
for (int i = 0; i < n; ++i) {
scanf("%d %d", &a[i], &b[i]);
tcnt += (a[i] + b[i] - 1) / b[i]; // 总共只能用tcnt次
}
int x = 0, r = INT_MIN; // x为最后一次升级最多可以提升的攻击力数
for (int i = 0; i < n; ++i) {
if (a[i] > r) {
r = a[i];
}
}
r = r + 1; // 取最大值+1作为初始右边界
int mid;
while (x < r) { // 二分法查找x的值,类似lower_bound
mid = x + (r - x + 1) / 2; // 使用此种方法防止出现mid = r - 1且check(r - 1)为true,x(mid)就无法大于等于r
if (check(mid)) { // 若可以第m次增加的攻击力大于mid
x = mid; // 则x至少为mid,查找右区间
} else {
r = mid - 1; // 否则,x必小于mid,再查找左区间
}
}
// 此时已找到升级m次可以达到的最大的攻击力增量x,即只要前m次攻击力增量>x,则一定采用其,直接加进att
for (int i = 0; i < n; i++) {
if (a[i] > x) { // 一定是大于,不能等于,因为不知道有多少选择是可以刚好等于x的,即一定存在至少m个大于等于x的攻击力增量,只是最后某些次为x
int cnt = (a[i] - x) / b[i] + 1; // 这里+1同理,因为第一次不会扣除b[i]
int last = a[i] - (cnt - 1) * b[i]; // 判断其最后一次是否刚好等于x
if (last == x) {
cnt--;
last += b[i];
}
if (m >= cnt) { // 剩余次数足够
att += (long long)(a[i] + last) * cnt / 2; // 等差数列直接算
m -= cnt;
} else { // 剩余次数不够,只能再加m次
cnt = m;
m = 0;
att += (long long)(a[i] + a[i] - (cnt - 1) * b[i]) * cnt / 2;
break;
}
}
}
printf("%lld\n", att + (long long)x * m);
return 0;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复