当前没有测试数据。

一、题目详细分析

1. 题目重述

小英雄需要击败 n 个怪物，要求其战斗力严格大于所有怪物的战斗力。小英雄可以使用法宝 k 次，每次将任意一个怪物的战斗力降低 100（最低降至 0）。我们需要找到小英雄完成任务所需的最小战斗力。

2. 核心思路：二分答案

这是一道典型的二分答案问题，原因如下：

• 单调性：若小英雄战斗力为 x 时能完成任务，那么所有大于 x 的战斗力也一定能完成任务；若 x 无法完成任务，那么所有小于 x 的战斗力也无法完成任务。
• 目标：找到满足条件的最小 x，因此可以通过二分查找在合理范围内快速定位答案。

3. 检查函数 check(x) 的设计

函数 check(x) 用于判断：当小英雄战斗力为 x 时，能否在 k 次法宝使用内让所有怪物战斗力小于 x。

具体逻辑：

• 遍历每个怪物的战斗力 a[i]：
  • 若 x > a[i]：无需使用法宝，跳过。
  • 若 x ≤ a[i]：计算需要多少次法宝操作能让 a[i] < x。
    • 操作次数公式：(a[i] - x) / 100 + 1（整数除法）。
    • 举例：a[i] = 300，x = 101，则 (300 - 101) = 199，199 / 100 = 1，+1 后得到 2 次操作（300 → 200 → 100，100 < 101）。
• 累加所有操作次数，若总次数 ≤ k，则 x 可行，返回 true；否则返回 false。

4. 二分边界与过程

• 左边界 l：最小可能的战斗力，初始为 1。
• 右边界 r：最大可能的战斗力，初始为 max(a[i]) + 1（最坏情况下不使用法宝，需要比最强怪物高 1 的战斗力）。
• 二分过程：
  • 取中间值 mid = (l + r) / 2。
  • 若 check(mid) == true：说明 mid 可行，尝试寻找更小的战斗力，更新答案 ans = mid，并将右边界左移 r = mid - 1。
  • 若 check(mid) == false：说明 mid 不可行，需要增大战斗力，将左边界右移 l = mid + 1。

5. 复杂度分析

• 时间复杂度：二分次数约为 log2(1e18) ≈ 60 次，每次 check 遍历 n 个怪物，总时间复杂度为 O(n log(max_a))，对于 n = 1e6 完全可通过。
• 空间复杂度：O(n) 用于存储怪物战斗力，符合题目要求。

二、代码详细注释

#include<bits/stdc++.h>
using namespace std;

// 变量说明：
// n：怪物数量
// m：法宝使用次数（对应题目中的k）
// a[]：存储每个怪物的战斗力
// ma：记录所有怪物中的最大战斗力
long long n, m, a[1000005], ma;

// 检查函数：判断当小英雄战斗力为x时，能否在m次内让所有怪物战斗力小于x
bool check(long long x) {
    long long cnt = 0; // 记录需要的法宝使用次数
    for (int i = 1; i <= n; i++) { // 遍历每个怪物
        if (x > a[i]) continue; // 如果x已经大于该怪物战斗力，无需操作
        // 计算需要多少次法宝操作能让a[i] < x
        // 公式：(a[i] - x) / 100 + 1（整数除法）
        cnt += (a[i] - x) / 100 + 1;
        if (cnt > m) return false; // 若次数超过m，直接返回false
    }
    return true; // 总次数≤m，返回true
}

int main() {
    // 输入优化：加速cin的读取速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 读取怪物数量n和法宝使用次数m
    cin >> n >> m;
    // 读取每个怪物的战斗力，并记录最大值ma
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ma = max(ma, a[i]);
    }

    // 二分查找初始化
    long long l = 1, r = ma + 1, ans = 1e18 + 10;
    // 二分主循环
    while (l <= r) {
        long long mid = (l + r) / 2; // 取中间值
        if (check(mid)) { // 若mid可行
            ans = mid; // 更新答案为mid
            r = mid - 1; // 尝试寻找更小的可行值，右边界左移
        } else {
            l = mid + 1; // 若mid不可行，增大战斗力，左边界右移
        }
    }

    // 输出最小战斗力
    cout << ans;
    return 0;
}

三、样例执行过程解析

以样例输入为例：

5 4
100 100 150 200 300

• 初始状态：l=1，r=301，ans=1e18+10。
• 二分过程（关键步骤）：
  • 当 mid=101 时，调用 check(101)：
    • 怪物1（100）：101>100，跳过。
    • 怪物2（100）：101>100，跳过。
    • 怪物3（150）：(150-101)/100 +1 = 49/100 +1 = 0+1=1 次。
    • 怪物4（200）：(200-101)/100 +1 = 99/100 +1=0+1=1 次。
    • 怪物5（300）：(300-101)/100 +1=199/100 +1=1+1=2 次。
    • 总次数：1+1+2=4，等于 m=4，返回 true。
  • 更新 ans=101，r=100，继续二分查找更小的可行值，但后续 check 会发现更小的值无法满足条件，最终 ans=101 为答案。