解题思路:  简化攻击力增加量的计算过程,确保每次升级后都按等差数列求和来计算总增加攻击力。


参考代码:

#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分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论