Luogu

LOJ

分析

我们画出每条路线的 $t-E$ 图像，大概是这个样子的（蓝色的是原函数，红色的是它的导数）：

感性理解一下可以知道，最后每条路径在其消耗的能量处的导数相同。

于是我们可以二分这个导数，然后把每段的速度求出来，算一下总能量是否 $\leq E_U$ 来 check。

现在考虑已知导数怎么算速度。我们有
$$
\begin{aligned}
\frac{\mathrm{d}t}{\mathrm{d}E}&=\frac{\mathrm{d}t}{\mathrm{d}v}\div \frac{\mathrm{d}E}{\mathrm{d}v}\\
&=-\frac{s}{v^2}\div 2k(v-v')s\\
&=-\frac{1}{2kv^2(v-v')}
\end{aligned}
$$
这个东西在 $[v',+\infty)$ 上是单增的，所以同样可以二分出 $v$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;
const double eps=1e-13;

int n;
double E,s[N],k[N],v[N];

double calcv(double d,int x) {
    double L=max(0.0,v[x]),R=1e6;
    while (R-L>eps) {
        double mid=(L+R)/2;
        if (-1/(2*k[x]*mid*mid*(mid-v[x]))<d) L=mid;
        else R=mid;
    }
    return L;
}

double calcE(double d) {
    double res=0;
    for (int i=1;i<=n;++i) {
        double vv=calcv(d,i);
        res+=k[i]*(vv-v[i])*(vv-v[i])*s[i];
    }
    return res;
}

int main() {
    n=read(); scanf("%lf",&E);
    for (int i=1;i<=n;++i) scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
    double L=-1e9,R=0;
    while (R-L>eps) {
        double mid=(L+R)/2;
        if (calcE(mid)<=E) L=mid;
        else R=mid;
    }
    double ans=0;
    for (int i=1;i<=n;++i)
        ans+=s[i]/calcv(L,i);
    printf("%.8lf\n",ans);
    return 0;
}