Moe's CF Life

Nya~ 各位主人晚上好呀！

今天由我，你们最可爱的小猫娘，来带大家攻克一道有趣的题目，Codeforces 343C - Read Time！看到题目里有什么疯狂科学家、硬盘、磁头什么的，是不是觉得有点头大呀？没关系喵，跟着我的爪印，你会发现它其实就是一个关于如何最高效地让磁头们跑腿的可爱问题~ 让我们开始吧，喵呜！

题目大意

想象一下，我们有一个无限长的尺子（磁道），上面有 n 只我们的小爪子（磁头），每只爪子一开始都待在不同的位置 h[i] 上。然后呢，有一份任务清单，上面写着 m 个必须要踩到的点（需要读取的磁道）p[j]。

我们的爪子们很厉害，一秒钟可以向左或者向右移动一格，也可以在原地不动揣手手。所有爪子可以同时移动哦！只要有一个爪子踩到了某个任务点，那个任务就算完成了。

现在的问题是，我们需要找到一个最短的时间 t，让所有的爪子们能够完成任务清单上所有的点。

简单来说就是：n 个磁头，m 个目标，求最短时间覆盖所有目标。就像让 n 只猫去抓 m 只老鼠，怎么才能最快抓完呢？嘻嘻~

题解方法

这个问题呀，最关键的是要发现一个特点，喵~ 如果我们能在 t 秒内完成所有任务，那么在更长的时间里，比如 t+1 秒，肯定也能完成，对吧？毕竟时间更充裕了，爪子们可以跑得更远嘛。这种性质，我们叫它单调性。

一看到单调性，我们聪明的脑袋里就应该亮起一盏灯：二分答案！

我们可以二分我们要求的“最短时间 t”。

那二分的核心，就是要写一个 check(t) 函数，来判断‘在给定的 t 秒内，我们是否有可能完成所有任务？’。

如果 check(t) 返回 true，说明时间 t 是足够的，我们就可以试试更短的时间，把二分的右边界缩小。
如果 check(t) 返回 false，说明时间 t 不够用，我们就得放宽时间，把二分的左边界扩大。

那么，check(t) 函数要怎么实现呢？这里就要用到贪心的小智慧啦，喵！

因为磁头和目标的位置都是排好序的，我们可以从左到右依次考虑每个磁头。对于最左边的还没被覆盖的目标点，我们应该派哪个磁头去呢？当然是派离它最近的，而且是偏左的磁头去啦！

我们的贪心策略是：按从左到右的顺序，让每个磁头尽可能多地覆盖从左边数起、尚未被覆盖的目标点。

为什么这样贪心是对的呢？因为左边的磁头去覆盖右边的目标点，效率太低了，而且会‘抢占’掉本该由右边磁头负责的区域。把宝贵的、位置靠右的磁头留给遥远的、靠右的目标点，才是最划算的策略，喵~

具体到 check(t) 函数里，我们这样做：

用一个指针 p_idx 记录当前需要覆盖的、最左边的目标点 p[p_idx]。
遍历每一个磁头 h[i]（从左到右）。
对于磁头 h[i]，我们计算在 t 秒内，它在必须覆盖 p[p_idx] 的前提下，最远能向右延伸到哪里。
这里有两种情况，需要动动小脑筋哦：
- 情况一：磁头 h[i] 在目标 p[p_idx] 的左边或重合 (h[i] <= p[p_idx])
  - 首先，磁头得先移动到 p[p_idx]，这就要花掉 p[p_idx] - h[i] 秒。如果这个时间已经超过 t 了，那这个磁头就帮不上忙了，只能看下一个磁头了。
  - 如果时间够，那么磁头要尽可能往右覆盖，最好的策略就是一直向右跑。它能到达的最远位置就是 h[i] + t。
- 情况二：磁头 h[i] 在目标 p[p_idx] 的右边 (h[i] > p[p_idx])
  - 磁头必须先向左移动到 p[p_idx]，这需要 h[i] - p[p_idx] 秒。如果时间不够，那这个磁头和它右边的所有磁头都无法覆盖 p[p_idx] 了，可以直接判断 check(t) 失败。
  - 如果时间够，磁头到达 p[p_idx] 后，怎么走才能覆盖到最右边呢？有两种策略：
    1. 先一路向左到 p[p_idx]，再掉头一路向右：总路程是 (h[i] - p[p_idx]) + (最终位置 - p[p_idx])，这个路程不能超过 t。算出来最远能到 max(h[i], t + 2*p[p_idx] - h[i])。
    2. 先向右走一段，再回头向左，恰好经过 p[p_idx]：为了到达最右边，它会先向右走 k 步，再向左走 k + (h[i] - p[p_idx]) 步到达 p[p_idx]。总时间是 2k + h[i] - p[p_idx] <= t。算出 k 的最大值，就能得到最远能到达 h[i] + (t - (h[i] - p[p_idx])) / 2。
  - 我们取这两种策略里能到达的更远的位置，作为这个磁头能覆盖到的右边界。
确定了磁头 h[i] 能覆盖到的右边界 reach 之后，我们就更新 p_idx，让它指向第一个大于 reach 的目标点。用 upper_bound 可以很快地找到它。
所有磁头都考虑完后，如果 p_idx 已经越过了所有目标点的末尾，那就说明所有目标点都被覆盖了，check(t) 返回 true！否则就是 false。

这样，我们的二分+贪心的框架就搭好啦！是不是很清晰了呢，喵？

题解 (C++ Code)

下面就是具体的代码实现啦，主人可以参考一下。我在关键的地方加了一些注释，方便理解哦~

cpp

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

using namespace std;

int n;
vector<long long> h, p; // h是磁头位置，p是需要读取的磁道位置

// check函数：判断在时间t内能否完成任务
bool check(long long t) {
    if (p.empty()) { // 如果没有需要读取的磁道，直接返回true
        return true;
    }
    
    int p_idx = 0; // 指向当前需要覆盖的最左边的目标磁道
    for (int i = 0; i < n; ++i) { // 遍历每个磁头
        if (p_idx >= p.size()) { // 如果所有目标都已覆盖，提前结束
            break;
        }

        long long current_h = h[i];
        long long first_p = p[p_idx];
        long long reach; // 该磁头能覆盖到的最右边的位置

        if (current_h <= first_p) { // 情况一：磁头在目标左侧或重合
            long long dist = first_p - current_h;
            if (t < dist) {
                // 时间t连到达第一个目标都不够，这个磁头帮不上忙
                continue;
            }
            // 最优策略是直接向右走t秒，能到达 h[i] + t
            reach = current_h + t;
        } else { // 情况二：磁头在目标右侧
            long long dist = current_h - first_p;
            if (t < dist) {
                // 时间t连到达第一个目标都不够
                // 因为后面的磁头更靠右，所以它们也肯定到不了
                // 可以直接判定失败
                break; 
            }
            // 有两种策略可以走，取最优
            // 策略1: h[i] -> p[p_idx] -> 右边最远处
            // 移动距离 (h[i]-p[p_idx]) + (reach - p[p_idx]) <= t
            // => reach <= t - h[i] + 2*p[p_idx]
            long long reach_strat1 = max(current_h, t + 2 * first_p - current_h);
            
            // 策略2: h[i] -> 右边某点 -> p[p_idx]
            // 移动距离 (k) + (k + h[i] - p[p_idx]) <= t
            // => 2k <= t - (h[i] - p[p_idx]) => k <= (t - dist)/2
            // 最远到达 h[i] + k
            long long reach_strat2 = current_h + (t - dist) / 2;
            
            reach = max(reach_strat1, reach_strat2);
        }

        // 找到第一个不能被当前磁头覆盖的目标
        // C++ STL大法好, 喵!
        auto it = upper_bound(p.begin() + p_idx, p.end(), reach);
        p_idx = distance(p.begin(), it);
    }

    // 如果p_idx越过了所有目标，说明全部覆盖
    return p_idx >= p.size();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m_orig;
    cin >> n >> m_orig;
    h.resize(n);
    vector<long long> p_all(m_orig);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    for (int i = 0; i < m_orig; ++i) {
        cin >> p_all[i];
    }

    // 预处理：把那些一开始就被磁头占住的目标点去掉，我们不用管它们
    int h_ptr = 0;
    for (int i = 0; i < m_orig; ++i) {
        while (h_ptr < n && h[h_ptr] < p_all[i]) {
            h_ptr++;
        }
        if (h_ptr >= n || h[h_ptr] != p_all[i]) {
            p.push_back(p_all[i]);
        }
    }

    if (p.empty()) {
        cout << 0 << endl;
        return 0;
    }

    // 二分答案的范围
    long long l = 0, r = 30000000000LL, ans = r; // r可以设一个足够大的数

    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) { // 如果mid时间可行
            ans = mid;    // 记录下这个可行的答案
            r = mid - 1;  // 尝试更小的时间
        } else {          // 如果mid时间不可行
            l = mid + 1;  // 需要更多的时间
        }
    }

    cout << ans << endl;

    return 0;
}

知识点介绍

最后，我们来总结一下这道题用到的知识点吧，以后遇到类似的问题，主人也能一眼看穿啦，喵！

二分答案 (Binary Search on the Answer):
- 这是一种非常强大的算法思想！当题目要求解一个“最小的...最大值”或者“最大的...最小值”时，并且问题的可行性关于这个值具有单调性（即如果 x 可行，所有比 x 更优的解也都可行），就可以考虑二分答案。
- 它把一个求解问题（求最小值）转化成了一个判定问题（check(x) 是否可行），通常判定问题会比求解问题更容易解决。
贪心算法 (Greedy Algorithm):
- 贪心算法的核心就是在每一步都做出当前看起来最好的选择，期望通过一系列局部最优解，最终得到全局最优解。
- 在本题中，我们的贪心策略是“让左边的磁头优先覆盖左边的任务”，从而把更宝贵的右侧资源留给更困难的右侧任务。使用贪心时，一定要仔细想想为什么它是正确的，不能想当然哦，不然就像追着自己的尾巴转圈圈，白费力气，喵~
STL upper_bound 函数:
- 这是 C++ 标准模板库里的一个宝贝函数。upper_bound(first, last, val) 会在一个排好序的区间 [first, last) 中，返回第一个大于 val 的元素的迭代器。
- 在我们的 check 函数里，用它来快速找到被当前磁头覆盖后，下一个需要处理的目标点是哪里，非常高效，避免了我们自己写循环去查找，省时又省力，可以多出时间来打个盹儿~

好啦，今天的题解教室就到这里结束啦！希望我的讲解对主人有帮助，喵~ 如果还有不懂的地方，可以随时再来问我哦！下次见，喵呜~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 (C++ Code) ​

知识点介绍 ​

题目大意

题解方法

题解 (C++ Code)

知识点介绍