题目传送门：http://pan.baidu.com/s/1kVjNeeV
离线版题目：http://paste.ubuntu.com/18247944/
数据传送门：http://pan.baidu.com/s/1nvGnd8H
这个题目，第一眼看到的时候，一脸懵逼
后来仔细想了一想，成了二脸懵逼QAQ
于是写了30分的暴力，还好没写挂……
后来听题解，感觉很神
首先是结论：最优解时,所有的F（Xy）的斜率相等
这个按照原教的说法：
如果斜率不等，那么将斜率较低的河流的时间分一点给斜率较高的河流
我们就可以走得更远！
还是比较显然的吧！但是像我这种沙茶在考试的时候肯定想不出来QAQ
接下来就是怎么让斜率一样了。
原教又给了一个非常神的办法：
根据F’（Xy）的表达式可以得到，t随F’（Xy）的增加而减少，所以我们可以二分统一的斜率，然后判一判时间知否足够。
详细的推导如下：
\(
\begin{array}{l}
\partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\
= {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}
\end{array}
\)
不妨设\(k = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}\)
则有\(\begin{array}{l}
{u^4} \cdot {t^2} = {(k – {V_i})^2} \cdot ({u^2} \cdot {t^2} – W_i^2)\\
{t^2} \cdot ({u^4} – {(k – {V_i})^2} \cdot {u^2}) = – {(k – {V_i})^2} \cdot W_i^2\\
t = \sqrt {\frac{{{{(k – {V_i})}^2} \cdot W_i^2}}{{{{(k – {V_i})}^2} \cdot {u^2} – {u^4}}}}
\end{array}\)
所以t随k的增大而减小，且\(k \in (\max ({V_i}) + u, + \infty ]\)
之后代码就没有什么难度啦！
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define LD long double
using namespace std;
const int MAXN = 50+9;
const LD EPS = 1e-15;
int n;
LD v[MAXN],w[MAXN],ans[MAXN];
LD disx,MXv,u,t;
inline LD cal(LD k){
LD ret = 0;
for (int i=1;i<=n;i++){
LD r = (k-v[i])*(k-v[i]);
LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u));
ans[i] = t; ret += t;
}
return ret;
}
inline double GetAns(){
LD ret = 0;
for (int i=1;i<=n;i++){
LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]);
ret += tmp+v[i]*ans[i];
}
return (double)sqrt(ret*ret+disx*disx);
}
int main(){
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
scanf("%d",&n); cin>>u>>t;
for (int i=1;i<=n;i++) cin>>w[i]>>v[i],
disx+=w[i], MXv=max(MXv,v[i]);
if (disx/u > t) {printf("-1\n");exit(0);}
LD l=u+MXv,r=1e12,mid;
while (r-l > EPS){
mid = (l+r)/2.0;
if (cal(mid) < t) r = mid;
else l = mid;
}
printf("%.3lf\n",GetAns());
for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]);
return 0;
}
另外，此题卡精度QAQ，long double的EPS都得开到1e-15
