题解 | #qcjj寄快递#

1. 问题分析

该问题本质上是一个函数最优化问题。我们需要计算在二维平面上经过 个点的总耗时。由于每一段路径（两个相邻途径点之间）的缩放系数 是独立选择的，且互不影响，因此该问题具有最优子结构性质。

我们可以将全局最小化问题分解为 个独立的子问题：对于每一对相邻点，寻找一个非负实数 ，使得当次滑动的耗时最小。最后将所有段的最小耗时累加即可得到最终结果。

• 距离度量：欧几里得距离 。
• 耗时函数：对于距离 ，选择参数 后的耗时为 。
• 参数约束： 为非负浮点数 ()。
• 计算规模：，这要求算法的时间复杂度应为 ，即必须通过公式推导出的 策略来解决每一段的耗时计算，而不是使用迭代逼近或三分查找。

2. 数学推导

为了找到每一段的最优 ，我们需要对耗时函数进行从数学分析。

设距离为 ，目标函数为：

2.1 求导寻找极值点

为了方便求导，我们将指数底数 转换为自然底数 （此处标记为 以区别于距离 ）：

对 求一阶导数：

令 ，求驻点：

2.2 边界条件分析

由于物理意义限制， 必须非负 ()。我们需要判断计算出的极值点是否落在定义域内。 该函数是下凸函数（二阶导数 ），因此极值点即为最小值点。

• 情况 A：缩放有利

  当 时，计算出的 。 此时，最优策略是进行缩放。 将 代入原方程：

• 情况 B：直接滑动更优

  当 时，导数解出的 。 由于函数在 区间单调递减，而在 的定义域内，随着 增大函数值单调递增。 因此，最小值取在定义域的左边界 。 物理含义是：当两点距离非常近时，缩小比例尺和放大回来的时间成本（）已经超过了直接以最大比例尺滑动的节省时间，因此直接滑动 () 最快。

3. 复杂度分析

• 时间复杂度: 算法仅需遍历所有点一次。对于每对相邻点，计算欧式距离和代入时间公式均为 的数学运算。
• 空间复杂度: 仅需存储当前点和上一个点的坐标，以及累加的总时间，不需要额外的数组空间（假设流式读取输入，若一次性读取所有点则为 ）。

4. 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<double> x(n), y(n);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    const double ln2 = std::log(2.0);
    const double THRESHOLD = 1.0 / ln2;
    int prev = 0;
    auto getDist = [&](int prev, int cur) -> double {
        double dx = x[cur] - x[prev];
        double dy = y[cur] - y[prev];
        return std::sqrt(dx * dx + dy * dy);
    };

    double total = 0.0;
    for (int cur = 1; cur < n; cur++) {
        double dist = getDist(prev, cur);
        double t;
        if (dist <= THRESHOLD) {
            t = 2.0 * dist;
        } else {
            t = 2.0 * std::log(dist * ln2) / std::log(2.0) + 2.0 / ln2;
        }
        total += t;
        prev = cur;
    }

    cout << fixed << setprecision(10) << total << endl;
}