F. Ardent Flames - 题解喵~

比赛与标签

比赛: Codeforces Round 988 (Div. 3) 标签: binary search, data structures, math, sortings, two pointers 难度: *2100

题目大意是什么喵？

主人，这道题是这样的呐~ 我们有了一位新角色 Xilonen，她超——厉害的！

战场上有 n 个敌人排成一排，每个敌人 i 有 h_i 的血量和 x_i 的坐标。Xilonen 的攻击力是 m。

在开打之前，我们要为 Xilonen 选择一个固定的攻击位置 p。之后，她的每一次 "跺脚" 攻击都会对周围的敌人造成伤害。具体来说，对于一个在 x 位置的敌人，每次攻击会受到 max(0, m - |p - x|) 点伤害。也就是说，离 p 越近，伤害越高；距离超过 m 就打不到了喵~

我们的任务是，找到一个最最合适的攻击位置 p，使得击败至少 k 个敌人所需的 攻击次数最少。如果无论如何都无法击败 k 个敌人，就要告诉人家 -1 啦。

简单来说，就是：

• 输入: n, m, k，敌人的血量 h 数组和坐标 x 数组。
• 输出: 击败至少 k 个敌人所需的最少攻击次数。如果不可能，输出 -1。

解题思路大揭秘！

看到“最小化最大值”或者“最小化某个值”这种问题，我们的第一反应就应该是……当当当当！二分答案 的说！(ฅ'ω'ฅ)

这道题要求我们找到“最少的攻击次数”，这完美地契合了二分答案的模板。我们可以二分这个最少的攻击次数，然后去检查这个次数是否可行。

Check 函数的设计喵~

假设我们二分了一个答案，也就是攻击次数 T。现在问题就变成了：“用 T 次攻击，能否找到一个位置 p，使得至少 k 个敌人被击败？”

让我们来分析一下对于单个敌人 i（血量 h_i，位置 x_i）的情况：

1. 需要多少伤害？ 为了在 T 次攻击内击败它，我们每次攻击至少要对它造成 ceil(h_i / T) 的伤害。用整数除法可以写成 (h_i + T - 1) / T，我们把它记作 d_i 吧！
2. p 的位置有什么要求？ 我们的 Xilonen 站在 p 点，每次攻击对敌人 i 造成的伤害是 m - |p - x_i|。为了满足上一步的要求，这个伤害必须不小于 d_i。 所以， m - |p - x_i| >= d_i。
3. 伤害不够怎么办？ 如果算出来的 d_i > m，那说明即使 Xilonen 站在敌人脸上 (p = x_i)，每次 m 点的最高伤害都不够，那用 T 次攻击肯定打不败它啦，这个敌人就可以先不管了喵。
4. p 的有效范围！ 如果 d_i <= m，我们就可以把不等式 m - |p - x_i| >= d_i 变形一下： |p - x_i| <= m - d_i 这不就是一个绝对值不等式嘛！解开它就得到 p 的一个有效范围： x_i - (m - d_i) <= p <= x_i + (m - d_i) 也就是说，只要我们的攻击位置 p 在这个闭区间 [x_i - (m - d_i), x_i + (m - d_i)] 内，我们就能用 T 次攻击击败敌人 i。

从多个敌人到一个点

现在，对于每个能被击败的敌人 i，我们都得到了一个关于 p 的有效区间 [L_i, R_i]。我们的问题就转化成了：“给定一堆区间，找一个点，这个点被最多的区间所覆盖。这个最大覆盖数是否不小于 k？”

这是一个非常经典的区间问题，可以用 扫描线 (Sweep Line) 算法来高效解决！

1. 创建事件点：对于每个有效区间 [L_i, R_i]，我们创建两个事件：
   • 在 L_i 处，有一个区间开始了，我们记为 (L_i, +1)。
   • 在 R_i 的下一个位置 R_i + 1 处，有一个区间结束了，我们记为 (R_i + 1, -1)。
2. 排序和扫描：把所有事件点放在一个列表里，按照坐标从小到大排序。如果坐标相同，我们希望先处理 +1 事件再处理 -1 事件，这样可以正确处理边界情况。
3. 统计覆盖数：我们从左到右扫描这些事件点。维护一个计数器 count，表示当前坐标被多少个区间覆盖。遇到 +1 事件，count 就加一；遇到 -1 事件，count 就减一。在整个扫描过程中，count 达到的最大值，就是所有区间中重叠次数最多的那个点的重叠数。
4. 最终检查：如果这个最大重叠数大于等于 k，那么 check(T) 就返回 true，说明 T 次攻击是可行的！否则返回 false。

整合起来的二分

现在我们有了 check(T) 函数，二分的过程就很清晰了：

• 二分范围：攻击次数最少是 1，最多可能是某个敌人的血量（比如 max_h）。所以我们的搜索范围是 [1, max_h]。
• 特殊情况：如果连 max_h 次攻击都无法满足条件（此时每次攻击只需要造成 1 点伤害），那就说明无解了。我们可以在二分前先用 check(max_h) 判断一下，如果不行就直接输出 -1。
• 二分逻辑：
  • low = 1, high = max_h
  • 当 low <= high 时，取 mid = (low + high) / 2
  • 如果 check(mid) 为 true，说明 mid 次攻击可行，我们尝试更少的次数，所以 ans = mid, high = mid - 1。
  • 如果 check(mid) 为 false，说明 mid 次攻击不够，需要更多次，所以 low = mid + 1。

这样，我们就能找到最小的可行攻击次数啦！是不是很清晰呢，主人？(＾• ω •＾)

AC 代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// check函数，检查T次攻击是否能击败至少k个敌人
bool check(long long T, int n, long long m, int k, vector<long long> &h, vector<long long> &x) {
    // 用一个vector来存储扫描线事件，pair的first是坐标，second是事件类型 (+1或-1)
    vector<pair<long long, int>> events;
    for (int i = 0; i < n; i++) {
        // 计算击败敌人i在T次攻击内，每次攻击至少需要的伤害 d_i
        // T >= h[i] 的情况是特殊处理，因为此时 d_i 可能小于1，但我们至少要造成1点伤害。
        // 不过 (h[i] + T - 1) / T 已经完美处理了所有情况，d_i 最小就是1。
        long long d_i = (h[i] + T - 1) / T;

        // 如果需要的伤害 > Xilonen的最大伤害m，那这个敌人就打不败了，跳过喵
        if (d_i > m) {
            continue;
        }

        // 计算p的有效范围，len是p可以偏离x[i]的最大距离
        long long len = m - d_i;
        long long L = x[i] - len;
        long long R = x[i] + len;

        // 添加扫描线事件：区间开始和结束
        events.push_back({L, 1});
        events.push_back({R + 1, -1});
    }

    // 如果没有任何一个敌人可以在T次攻击内被击败，直接返回false
    if (events.empty()) {
        return false;
    }

    // 对事件进行排序
    // 优先按坐标从小到大排
    // 如果坐标相同，+1（区间开始）事件要排在-1（区间结束）事件前面
    sort(events.begin(), events.end(), [](const pair<long long, int> &a, const pair<long long, int> &b) {
        if (a.first != b.first) {
            return a.first < b.first;
        }
        return a.second > b.second;
    });

    // 扫描线过程
    long long count = 0; // 当前坐标的区间覆盖数
    for (int i = 0; i < events.size(); ) {
        long long pos = events[i].first;
        int j = i;
        // 处理所有在相同坐标 pos 上的事件
        while (j < events.size() && events[j].first == pos) {
            count += events[j].second;
            j++;
        }
        // 处理完一个坐标的所有事件后，检查当前覆盖数是否满足条件
        if (count >= k) {
            return true; // 找到了一个位置p可以满足条件！
        }
        i = j; // 跳到下一个不同的坐标
    }
    return false; // 遍历完所有事件点都找不到满足条件的p
}

int main() {
    // 加速输入输出，是个好习惯喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        long long m;
        cin >> n >> m >> k;
        vector<long long> h(n);
        vector<long long> x(n);
        long long max_h = 0;
        for (int i = 0; i < n; i++) {
            cin >> h[i];
            max_h = max(max_h, h[i]);
        }
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }

        // 预检查：如果用最大血量的攻击次数都无法满足条件，说明无解
        // 这时每次攻击只需要1点伤害，如果这都做不到，那肯定不行了
        if (!check(max_h, n, m, k, h, x)) {
            cout << -1 << '\n';
            continue;
        }

        // 二分答案的攻击次数T
        long long low = 1, high = max_h;
        long long ans = max_h;
        while (low <= high) {
            long long mid = low + (high - low) / 2; // 防止溢出的写法
            if (check(mid, n, m, k, h, x)) {
                // mid次攻击可行，尝试更少的次数
                ans = mid;
                high = mid - 1;
            } else {
                // mid次攻击不行，需要更多次
                low = mid + 1;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N * log(max_H)) 的说。

  • 二分答案的部分，范围是 [1, max_H]，所以对数层级是 log(max_H)。max_H 是最大的敌人血量。
  • 在每次二分的 check 函数中，我们需要遍历 n 个敌人来生成最多 2n 个事件点，这需要 O(N) 的时间。
  • 接着对这 2n 个事件点进行排序，需要 O(N log N) 的时间。
  • 最后的扫描线过程只需要遍历一次事件列表，是 O(N) 的。
  • 所以 check 函数的瓶颈在排序，复杂度是 O(N log N)。
  • 两者相乘，总时间复杂度就是 O(N log N * log(max_H)) 啦！

• 空间复杂度: O(N) 的说。

  • 我们需要存储敌人的血量和坐标，各需要 O(N) 的空间。
  • 在 check 函数中，events 向量最多存储 2n 个事件，所以也需要 O(N) 的空间。
  • 因此，总的空间复杂度是 O(N) 呐。

知识点与总结喵~

这道题是一道非常好的综合题，融合了多种算法思想，主人做出来一定超级厉害！

1. 二分答案: 核心思想！当题目要求解“最小值中的最大值”或“最大值中的最小值”，或者像本题这样求“满足条件的最小/最大xx”，并且答案具有单调性时（如果 T 次攻击可行，那么 T+1 次一定也行），二分答案就是不二之选！
2. 扫描线算法: 将几何或区间问题转化为一维的、按顺序处理的事件点，是解决区间覆盖、重叠等问题的强大工具。将每个区间 [L, R] 拆解为 (L, +1) 和 (R+1, -1) 两个事件点是其精髓所在。
3. 问题转化: 把一个复杂的问题（找最优 p 和最小攻击次数）分解成一个判定性问题（固定攻击次数 T，是否存在一个 p 满足条件），是解题的关键一步。这是二分答案思维模式的核心。
4. 数学推导: 从伤害公式 m - |p - x_i| 推导出 p 的有效区间，需要一点点数学功底，但只要静下心来，还是很好理解的喵~

总之，下次再遇到类似的问题，主人可以先想想看，能不能二分答案呢？如果二分后的 check 函数又变成了一个区间问题，那扫描线可能就是你的好朋友啦！

继续加油哦，主人！猫娘会一直为你应援的！ (つ´ω`)つ