最小差值 - 题解

标签与难度

标签: 数学, 分段函数, 绝对值函数, 排序, 扫描线, 前缀和 难度: 2100

题目大意喵~

你好呀，指挥官！这道题是这样的喵~

我们有两个整数数组，一个叫 a，有 n 个数；另一个叫 b，有 m 个数。我们的任务是，在 $-2 \times 10^9$ 到 $2 \times 10^9$ 的范围内，找到一个整数 k，让下面这个式子的值变得最小最小，就像猫猫 curled up in a ball 一样小，喵~

$$D(k) = \left| \left(\sum_{i=1}^{n} |a_i - k|\right) - \left(\sum_{j=1}^{m} |b_j - k|\right) \right|$$

如果有很多个 k 都能得到这个最小的值，我们要输出其中最小的那个 k 哦！

简单来说，就是找一个点 k，让它到所有 a 中点的距离之和，与它到所有 b 中点的距离之和，这两者之间的差距最小。

解题思路分析

这道题看起来好多数学符号，可能会有点吓人，但别怕，让我带你一步步把它分解开，就会发现它其实是一只温顺的小猫咪~ 呐！

首先，我们把这个复杂的式子拆成两部分来看。 令 $S_a(k) = \sum_{i=1}^{n} |a_i - k|$，这代表点 k 到数组 a 中所有点的距离之和。 令 $S_b(k) = \sum_{j=1}^{m} |b_j - k|$，这代表点 k 到数组 b 中所有点的距离之和。 我们最终的目标，就是最小化 $|S_a(k) - S_b(k)|$。

函数 $S(k)$ 的小秘密

让我们先只研究 $S_a(k)$ 这个函数。这是一个非常经典的函数模型，它的几何意义是数轴上一点 k 到多个定点 $a_1, a_2, \dots, a_n$ 的距离和。这个函数的图像是连续的、分段线性的并且是凸的（像一个碗一样）。

它的斜率（也就是函数的变化率）只会在 k 等于某个 $a_i$ 的时候才会改变。这些点 $a_i$ 就是我们所说的临界点或者说拐点。

举个栗子，如果 a = {1, 5}，那么 $S_a(k) = |1-k| + |5-k|$。

• 当 $k < 1$ 时, $S_a(k) = (1-k) + (5-k) = 6 - 2k$，斜率是 $-2$。
• 当 $1 \le k < 5$ 时, $S_a(k) = (k-1) + (5-k) = 4$，斜率是 $0$。
• 当 $k \ge 5$ 时, $S_a(k) = (k-1) + (k-5) = 2k - 6$，斜率是 $2$。

你看，斜率在 k=1 和 k=5 的时候发生了变化。每当 k 从左到右越过一个 $a_i$ 点，函数 $S_a(k)$ 的斜率就会增加 2。为什么是 2 呢？因为 $|x-k|$ 在 $x$ 点的导数从 -1 变成了 +1，变化量是 2 嘛。

我们的目标函数 $G(k) = S_a(k) - S_b(k)$

$S_a(k)$ 和 $S_b(k)$ 都是分段线性函数，那么它们的差 $G(k) = S_a(k) - S_b(k)$ 自然也是一个分段线性函数。它的临界点就是所有 $a_i$ 和 $b_j$ 的集合。

在任意两个相邻的临界点之间的开区间 $(p_1, p_2)$ 内，$G(k)$ 是一条直线，可以表示为 $G(k) = C \cdot k + D$，其中 $C$ 是斜率， $D$ 是截距。

扫描线大法，启动！

既然 $G(k)$ 是分段线性的，我们就可以用“扫描线”的思想来解决问题！想象我们有一根扫描线（其实就是变量 k），从负无穷向正无穷扫过去。我们只需要在每个临界点更新函数的斜率和截距，然后分析每一段区间里的最小值就行啦。

1. 收集临界点: 把所有 $a_i$ 和 $b_j$ 都看作是“事件点”。当我们的扫描线 k 经过一个 $a_i$ 时， $S_a(k)$ 的斜率增加 2，所以 $G(k)$ 的斜率也增加 2。当 k 经过一个 $b_j$ 时，$S_b(k)$ 的斜率增加 2，所以 $G(k)$ 的斜率减少 2。 我们可以创建一个事件列表，每个事件包含 {临界点坐标, 斜率变化量}。对于 $a_i$，事件是 {a_i, +2}；对于 $b_j$，事件是 {b_j, -2}。

2. 排序事件: 将所有事件点按坐标从小到大排序。

3. 初始化: 在扫描线 k 到达第一个临界点之前（即 $k \to -\infty$），我们来计算一下 $G(k)$ 的初始形态。

   • $S_a(k) = \sum_{i=1}^n (a_i - k) = (\sum a_i) - n \cdot k$
   • $S_b(k) = \sum_{j=1}^m (b_j - k) = (\sum b_j) - m \cdot k$
   • $G(k) = S_a(k) - S_b(k) = ((\sum a_i) - (\sum b_j)) + (m-n)k$ 所以，初始斜率 slope 是 $m-n$，初始截距 intercept 是 $\sum a_i - \sum b_j$。

4. 扫描与更新: 我们从左到右遍历排好序的事件点。设当前事件点坐标为 p，上一个事件点坐标为 last_p。

   • 分析区间 [last_p, p): 在这个区间内，$G(k)$ 是线性的：$G(k) = \text{slope} \cdot k + \text{intercept}$。我们要找 $|G(k)|$ 的最小值。
     • 如果 slope == 0，则 $G(k)$ 是常数 intercept。最小值为 |intercept|，在整个区间都能取到。为了让 k 最小，我们检查区间的左端点 last_p。
     • 如果 slope != 0，则 $|G(k)|$ 是一个V字形。最小值在顶点 $k_0 = -\text{intercept} / \text{slope}$ 处取得。
       • 我们需要检查的候选 k 值就包括区间的两个端点 last_p 和 p-1，以及顶点附近的整数 $\lfloor k_0 \rfloor$ 和 $\lceil k_0 \rceil$（如果它们落在区间 [last_p, p) 内的话）。
       • 实际上，因为 $|G(k)|$ 在这个区间内是单调的（或者先减后增），最小值一定在区间的端点或者顶点处取得。所以我们只需要检查 last_p 和 p-1 就足够覆盖端点的情况了，再额外检查一下顶点附近的整数。
   • 更新状态: 当扫描线越过点 p 后，斜率和截距需要更新以进入下一个区间。
     • slope_new = slope_old + slope_change_at_p
     • 为了保证函数 $G(k)$ 在点 p 处是连续的，我们需要调整截距。 $G_{old}(p) = \text{slope}_{old} \cdot p + \text{intercept}_{old}$$G_{new}(p) = \text{slope}_{new} \cdot p + \text{intercept}_{new}$ 因为 $G_{new}(p) = G_{old}(p)$，所以： $\text{intercept}_{new} = \text{intercept}_{old} + (\text{slope}_{old} - \text{slope}_{new}) \cdot p = \text{intercept}_{old} - (\text{slope\_change\_at\_p}) \cdot p$ 这个更新规则非常关键，喵~

5. 追踪答案: 在整个扫描过程中，我们维护一对变量 (min_diff, best_k)，记录遇到的最小差值和对应的最小 k。每次检查候选 k 时，都计算出 $|G(k)|$ 的值并更新我们的答案。

通过这个方法，我们就能高效地找到全局最优解啦！是不是很酷，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮助你理解~

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

using namespace std;

// 定义事件结构体，表示在某个点发生的斜率变化
struct Event {
    long long point;
    int slope_change;

    // 为了排序，重载小于运算符
    bool operator<(const Event& other) const {
        if (point != other.point) {
            return point < other.point;
        }
        return slope_change < other.slope_change;
    }
};

// 全局变量，用于存储最小差值和对应的k
long long min_difference = numeric_limits<long long>::max();
long long result_k = 0;

// 当前函数的斜率和截距
long long current_slope = 0;
long long current_intercept = 0;

// 检查一个候选的k值，并更新全局最优解
void check_candidate(long long k) {
    // 题目要求k在[-2e9, 2e9]范围内
    const long long k_min = -2000000000LL;
    const long long k_max = 2000000000LL;
    if (k < k_min || k > k_max) {
        return;
    }

    // 计算当前k对应的函数值 G(k) = slope * k + intercept
    // 为了防止溢出，使用 __int128
    __int128 current_value = (__int128)current_slope * k + current_intercept;
    long long diff = abs((long long)current_value);

    if (diff < min_difference) {
        min_difference = diff;
        result_k = k;
    } else if (diff == min_difference) {
        result_k = min(result_k, k);
    }
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n);
    vector<long long> b(m);
    vector<Event> events;

    long long sum_a = 0, sum_b = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum_a += a[i];
        events.push_back({a[i], 2}); // a_i 贡献 +2 的斜率变化
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        sum_b += b[i];
        events.push_back({b[i], -2}); // b_j 贡献 -2 的斜率变化
    }

    // 排序所有事件点
    sort(events.begin(), events.end());

    // 初始化扫描线状态
    // G(k) = (sum_a - sum_b) + (m - n) * k
    current_slope = (long long)m - n;
    current_intercept = sum_a - sum_b;
    
    // 初始检查范围的左边界
    check_candidate(-2000000000LL);

    long long last_point = -2000000000LL;

    // 开始扫描线
    for (const auto& event : events) {
        long long current_point = event.point;
        
        // --- 分析区间 [last_point, current_point) ---
        if (last_point < current_point) {
            // 检查区间端点
            check_candidate(last_point);
            check_candidate(current_point - 1);
            check_candidate(current_point);

            // 如果斜率不为0，检查V字形的顶点
            if (current_slope != 0) {
                // 顶点 k0 = -intercept / slope
                long long k0 = -floor((__int128)current_intercept / current_slope);

                // 检查顶点附近的整数
                for (long long k_cand = k0 - 2; k_cand <= k0 + 2; ++k_cand) {
                    if (k_cand >= last_point && k_cand < current_point) {
                        check_candidate(k_cand);
                    }
                }
            }
        } else { // last_point == current_point
             check_candidate(last_point);
        }

        // --- 更新状态以进入下一个区间 ---
        // G_new(k) = slope_new * k + intercept_new
        // G_old(p) = slope_old * p + intercept_old
        // G_new(p) = G_old(p)
        // (slope_old + change) * p + intercept_new = slope_old * p + intercept_old
        // intercept_new = intercept_old - change * p
        current_intercept -= (long long)event.slope_change * event.point;
        current_slope += event.slope_change;
        
        last_point = current_point;
    }
    
    // 检查最后一个区间 [last_point, 2e9] 的右边界
    check_candidate(2000000000LL);


    cout << result_k << endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O((N+M) \log(N+M))$ 主要的时间开销在于对 events 列表的排序。这个列表的大小是 $N+M$。排序需要 $O((N+M) \log(N+M))$ 的时间。之后的扫描线过程是线性的，遍历一次所有事件，复杂度为 $O(N+M)$。所以总复杂度由排序决定。

• 空间复杂度: $O(N+M)$ 我们需要一个 events 列表来存储所有的临界点信息，其大小为 $N+M$。因此，空间复杂度是 $O(N+M)$。

知识点总结

这道题真是一次有趣的冒险，对吧？我们用到的主要工具有：

1. 函数性质分析: 理解 $S(k) = \sum |x_i - k|$ 是一个分段线性凸函数是解题的第一步。这是解决这类绝对值和问题的关键钥匙，喵~
2. 扫描线算法: 将离散的点作为事件，按顺序处理，从而将一个全局问题转化为一系列局部问题。这是一种非常强大和通用的思想，在计算几何和很多其他领域都有应用。
3. 分段函数处理: 我们的目标函数 $G(k)$ 是分段线性的。扫描线算法让我们能在每个线性片段上，准确地找到最优解的候选点（端点和顶点）。
4. 精度与数据范围: 题目中的数值很大，计算过程中可能会出现中间值超过 long long 的情况（比如 slope * k），使用 __int128 来进行计算可以避免溢出，保证结果的正确性。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦！一起加油，变得更强，喵！ (ฅ'ω'ฅ)