自动搬运

查看原文

来自洛谷，原作者为

	SatoruXia 欢迎加入 INFOI！111309！||只有不知好歹的家伙才敢叫我大佬||世界的真理由我解明||支持互关，小号必关||基尼奇&那刻夏&莱欧斯利&艾尔海森厨||音游玩家，初二OIer，初次见面，祝我们合作愉快。

搬运于2025-08-24 23:15:01，当前版本为作者最后更新于2025-05-01 22:09:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑使用贪心加二分。
首先发现输入量较大，考虑输入优化。
其次想出思路：每次均选用当前升级最多的升级方式，随后将其减小并计算总值，类似于多路归并问题。思路没错，但数据量使模拟不现实。
观察算法标签，发现“二分”。因此得到新思路：在操作次数符合要求的情况下，必有一界限，或者叫阈值，使所有升级的攻击力均大于此阈值。因为每种升级方式每次升级的攻击力均按等差数列递减，因此用二分查找即可确保找出的阈值尽可能大。随后进行贪心，跳过所有小于阈值的升级方式，计算总升级次数。
还要值得注意的一点是：总升级次数可能大于规定操作次数。因此在输出时应添加判断：当攻击力超过规定时，删掉最小的（即升级攻击力等于阈值的）操作方式。然后输出即可。
代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int N, M, A[MAX_N], B[MAX_N], max_A = 0;//打擂台的擂主
int main() {
    //读入优化，提升效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //初始化
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        max_A = max(max_A, A[i]);//打擂台
    }
    //二分查找
    int left = 0, right = max_A, best_x = 0;//定义范围
    while (left <= right) {
        int mid = (left + right) / 2;
        long long total = 0;//攻击总量
        for (int i = 0; i < N; ++i)
            if (A[i] >= mid)
                total += (A[i] - mid) / B[i] + 1;
        if (total >= M) best_x = mid, left = mid + 1;//寻找最优阈值，即越大越好
        else right = mid - 1;//左闭右闭的写法
    }
    //贪心
    long long tot = 0, cnt = 0;//所有选中总攻击力，实际选中总攻击力（均可超过M次）
    for (int i = 0; i < N; ++i) {
        if (A[i] < best_x) continue;//即攻击力超过阈值才会升级
        int k = (A[i] - best_x) / B[i] + 1;
        cnt += k;
        tot += k * (2LL * A[i] - (k - 1) * B[i]) / 2;//等差数列求和，运算时不乘ll会爆
    }
    //输出
    //简单来说，当攻击力超过规定时，删掉最小的
    cout << tot - (cnt > M ? (cnt - M) * best_x : 0);//也可用if语句代替
    return 0;
}