loj2671. 「NOI2012」骑行川藏

题意

给出\(n\)段路，每段路有三个参数\(s_i, k_i, v_i\)，分别表示这段路的长度，风阻系数以及风速，若某一小段路（可以任意短）以速度\(\mathcal V_i\)匀速通过，则受到的风阻的大小为\(F = k_i (\mathcal V_i ? v_i) ^ 2\)，消耗能量为\(E = k_i (\mathcal V_i ? v_i) ^ 2 s_i\)，保证\(\sum_{i} E_i \leq E_u\)的前提下，求最短时间。

题解

由**的猜测可得，在每一段路上始终匀速运动，一定是最优解的一种。证明？先感性理解。

这样，问题变成

\[ \mathrm {Minimize \ } \sum \frac{s_i}{\mathcal V_i} \\mathrm {s.t. \ } \sum k_i s_i (\mathcal V_i - v_i) ^ 2 = E_u \\]

这就变成了

\[ \mathrm {Minimize \ } g(x_1, x_2, \ldots x_k) \\mathrm {s.t. \ } f(x_1, x_2, \ldots, x_k) = 0 \\]

这是一个拉格朗日乘子法解决的问题。

考虑在这题中，我们令拉格朗日函数
\[ L(\mathcal V_i, \lambda) = f(\mathcal V_i) - \lambda g(\mathcal V_i) \]
（有\(n\)个这样的函数）
令其对\(\mathcal V_i\)的偏导为\(0\)，则
\[ \frac{\partial L(\mathcal V_i, \lambda)}{\partial \mathcal V_i} = -\frac {s_i}{\mathcal V_i ^ 2} + 2 \lambda s_i k_i (\mathcal V_i - v_i) = 0 \]
则解得
\[ \lambda = \frac{1}{2 k_i \mathcal V_i ^ 2 (\mathcal V_i - v_i)} \]
由于\(\lambda\)随着\(\mathcal V_i\)递增而递减，\(f =\sum k_i s_i (\mathcal V_i - v_i) ^ 2 - E_u\)随着\(\mathcal V_i\)的递增而递增（因为题目中有隐含条件，要满足\(\mathcal V_i > v_i\)），则\(f\)随着\(\lambda\)的递增而递减。
因此只要二分check()一个\(\lambda\)，之后二分求出\(\mathcal V_i\)，check()返回值就是判断\(f\)是否小于等于\(0\)。
复杂度\(\mathcal O(n \log ^ 2 V)\)。

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-14, inf = 1e5;
const int N = 1e4 + 5;
int n; db E, s[N], k[N], _v[N], v[N];
bool check (const db &lambda) {
    for (int i = 1; i <= n; ++i) {
        db l = max(0.0, _v[i]), r = inf, mid, lv = 1.0 / (2.0 * k[i] * lambda);
        while (r - l >= eps) {
            mid = (l + r) / 2;
            mid * mid * (mid - _v[i]) > lv ? r = mid : l = mid;
        }
        v[i] = mid;
    }
    db e = 0;
    for (int i = 1; i <= n; ++i) {
        e += k[i] * s[i] * pow(v[i] - _v[i], 2);
    }
    return e <= E;
}
int main () {
    cin >> n >> E;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i] >> k[i] >> _v[i];
    }
    db l = 0, r = inf, mid;
    while (r - l >= eps) {
        mid = (l + r) / 2;
        check(mid) ? r = mid : l = mid;
    }
    db ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += s[i] / v[i];
    }
    cout.setf(ios :: fixed);
    cout << setprecision(6) << ans << endl;
    return 0;
}

loj2671. 「NOI2012」骑行川藏

原文：https://www.cnblogs.com/psimonw/p/11668315.html