2671. 「NOI2012」骑行川藏 题解

问题分析

我们面临一个带约束的最优化问题：

• 有 $N$ 段路，每段路长度 $s_i$，风阻系数 $k_i$，风速 $v_i'$
• 在第 $i$ 段路以速度 $v_i$ 匀速骑行，消耗能量 $E_i = k_i (v_i - v_i')^2 s_i$
• 总能量限制：$\sum_{i=1}^N E_i \le E_U$
• 目标：最小化总时间 $T = \sum_{i=1}^N \frac{s_i}{v_i}$

根据题目提示，存在最优解满足每段路都匀速骑行，因此我们只需要为每段路选择一个最优速度 $v_i$。

---

数学模型

这是一个约束优化问题：

$$\begin{aligned} \min &\quad T = \sum_{i=1}^N \frac{s_i}{v_i} \\ \text{s.t.} &\quad \sum_{i=1}^N k_i (v_i - v_i')^2 s_i \le E_U \\ &\quad v_i > \max(0, v_i') \quad (\text{速度必须为正且能前进}) \end{aligned} $$

由于能量约束通常在最优点处会取等号（不浪费能量），我们可以将不等式约束变为等式：

$$\sum_{i=1}^N k_i (v_i - v_i')^2 s_i = E_U$$

---

拉格朗日乘数法

构造拉格朗日函数：

$$L(v_1, \dots, v_N, \lambda) = \sum_{i=1}^N \frac{s_i}{v_i} + \lambda \left( \sum_{i=1}^N k_i (v_i - v_i')^2 s_i - E_U \right) $$

对 $v_i$ 求偏导并令为 0：

$$\frac{\partial L}{\partial v_i} = -\frac{s_i}{v_i^2} + 2\lambda k_i s_i (v_i - v_i') = 0 $$

化简得：

$$-\frac{1}{v_i^2} + 2\lambda k_i (v_i - v_i') = 0$$

即：

$$2\lambda k_i v_i^2 (v_i - v_i') = 1 \quad (1)$$

---

方程求解

对于给定的 $\lambda > 0$，方程 (1) 是一个关于 $v_i$ 的三次方程：

$$2\lambda k_i v_i^2 (v_i - v_i') - 1 = 0$$

展开：

$$2\lambda k_i v_i^3 - 2\lambda k_i v_i' v_i^2 - 1 = 0 $$

由于 $\lambda > 0$，$k_i > 0$，这个三次方程有唯一正解（因为函数 $f(v) = 2\lambda k_i v^2 (v - v_i')$ 在 $v > \max(0, v_i')$ 时单调递增）。

我们可以用牛顿迭代法求解：

$$v \leftarrow v - \frac{2\lambda k_i v^2 (v - v_i') - 1}{6\lambda k_i v^2 - 4\lambda k_i v_i' v} $$

初始值可取 $v = \max(v_i' + 1, 1)$。

---

确定 $\lambda$

$\lambda$ 是拉格朗日乘子，需要满足能量约束：

$$\sum_{i=1}^N k_i (v_i(\lambda) - v_i')^2 s_i = E_U $$

其中 $v_i(\lambda)$ 是方程 (1) 的解。

关键观察：

• 当 $\lambda \to 0^+$ 时，$v_i \to \infty$，总能量 $\to \infty$
• 当 $\lambda \to \infty$ 时，$v_i \to v_i'^+$，总能量 $\to 0$
• 总能量 $E(\lambda) = \sum_{i=1}^N k_i (v_i(\lambda) - v_i')^2 s_i$ 是 $\lambda$ 的单调递减函数

因此我们可以二分 $\lambda$ 来找到满足 $E(\lambda) = E_U$ 的值。

---

算法步骤

1. 二分 $\lambda$：

   • 下界 $l = 0$（但不能为 0，取一个很小的正数）
   • 上界 $r$ 足够大（如 $10^{10}$）
   • 迭代直到精度足够

2. 对于每个 $\lambda$：

   • 对每段路 $i$，用牛顿迭代法解方程 (1) 得到 $v_i$
   • 计算总能量 $E = \sum k_i (v_i - v_i')^2 s_i$

3. 调整二分边界：

   • 如果 $E > E_U$，说明 $\lambda$ 太小，需要增大 $\lambda$（$l \leftarrow \lambda$）
   • 如果 $E < E_U$，说明 $\lambda$ 太大，需要减小 $\lambda$（$r \leftarrow \lambda$）

4. 计算最终答案：

   • 找到满足精度要求的 $\lambda$ 后
   • 计算对应的 $v_i$
   • 总时间 $T = \sum \frac{s_i}{v_i}$

---

代码实现

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

const int MAXN = 10005;
const double EPS = 1e-12;  // 精度控制
const int MAX_ITER = 100;  // 牛顿迭代最大次数

int N;
double Eu;
double s[MAXN], k[MAXN], vp[MAXN];  // vp 表示 v_i'

// 牛顿迭代法求解 v_i
double solve_v(double lambda, int i) {
    double v = max(vp[i], 0.0) + 1.0;  // 初始值
    for (int iter = 0; iter < MAX_ITER; iter++) {
        double f = 2.0 * lambda * k[i] * v * v * (v - vp[i]) - 1.0;
        double df = 2.0 * lambda * k[i] * v * (3.0 * v - 2.0 * vp[i]);
        if (fabs(df) < EPS) break;
        double delta = f / df;
        v -= delta;
        if (v < vp[i]) v = vp[i] + EPS;  // 保证 v > vp[i]
        if (fabs(delta) < EPS) break;
    }
    return max(v, vp[i] + EPS);  // 保证 v > vp[i]
}

// 计算给定 lambda 下的总能量
double calc_E(double lambda) {
    double total_E = 0.0;
    for (int i = 1; i <= N; i++) {
        double v = solve_v(lambda, i);
        total_E += k[i] * (v - vp[i]) * (v - vp[i]) * s[i];
    }
    return total_E;
}

int main() {
    // 读入数据
    scanf("%d %lf", &N, &Eu);
    for (int i = 1; i <= N; i++) {
        scanf("%lf %lf %lf", &s[i], &k[i], &vp[i]);
    }
    
    // 二分 lambda
    double left = 0.0, right = 1e10;
    double lambda = 0.0;
    
    for (int iter = 0; iter < 200; iter++) {
        lambda = (left + right) * 0.5;
        double E = calc_E(lambda);
        
        if (E > Eu) {
            // lambda 太小，需要增大
            left = lambda;
        } else {
            // lambda 太大，需要减小
            right = lambda;
        }
        
        if (right - left < EPS) break;
    }
    
    // 计算最终答案
    double total_time = 0.0;
    for (int i = 1; i <= N; i++) {
        double v = solve_v(lambda, i);
        total_time += s[i] / v;
    }
    
    // 输出结果，保留足够小数位
    printf("%.10lf\n", total_time);
    
    return 0;
}

---

数值细节处理

1. 初始值选择

牛顿迭代的初始值取 $v = \max(v_i', 0) + 1$，保证收敛性。

2. 边界情况

• 当 $v_i' < 0$（逆风）时，$v$ 必须 $> 0$，不能直接取 $v_i'$
• 用 $v = \max(vp[i], 0.0) + 1.0$ 保证 $v > \max(0, v_i')$

3. 精度控制

• 二分迭代 200 次，精度可达 $10^{-10} \times 2^{-200} \approx 10^{-70}$，足够
• 牛顿迭代使用相对精度控制

4. 特殊情况

如果 $E_U = 0$，那么所有 $v_i = v_i'$（如果 $v_i' > 0$），但此时时间可能无限大。不过题目保证答案有限。

---

时间复杂度分析

• 二分 $\lambda$：$O(\log(\frac{1}{\epsilon}))$ 次，约 60-200 次
• 每次二分需要计算所有 $N$ 段路的 $v_i$：$O(N)$
• 每个 $v_i$ 用牛顿迭代法求解：常数次迭代（通常 5-10 次）

总复杂度：$O(N \cdot \log(\frac{1}{\epsilon}))$，对于 $N \le 10000$ 完全可行。

---

数学推导补充

方程 (1) 的推导过程：

$$\begin{aligned} \frac{\partial L}{\partial v_i} &= 0 \\ -\frac{s_i}{v_i^2} + 2\lambda k_i s_i (v_i - v_i') &= 0 \\ -\frac{1}{v_i^2} + 2\lambda k_i (v_i - v_i') &= 0 \\ 2\lambda k_i v_i^2 (v_i - v_i') &= 1 \end{aligned} $$

这解释了 $\lambda$ 的物理意义：它是能量的"价格"，$\lambda$ 越大，说明能量越"贵"，我们就会选择更接近 $v_i'$ 的速度以节省能量。

---

总结

本题的解题关键在于：

1. 识别出这是带约束的优化问题
2. 使用拉格朗日乘数法转化为无约束问题
3. 通过分析得到 $\lambda$ 的单调性，从而使用二分法
4. 对每个 $\lambda$ 用牛顿迭代法求解非线性方程