题意
给出(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;
}