题目传送门：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
Hi there mates, good post and nice urging commented at this
place, I am actually enjoying by these.
I love your blog.. very nice colors & theme.
Did you design this website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to create my own blog and would like to know where u got this
from. appreciate it
Hi, its nice article about media print, we all
be aware of media is a fantastic source of facts.
Howdy! I could have sworn I’ve been to this site before but after checking through some of the post I realized it’s new to me.
Nonetheless, I’m definitely delighted I found it and I’ll be bookmarking
and checking back often!
Hi there! This article couldn’t be written any better!
Reading through this article reminds me of my previous roommate!
He always kept talking about this. I’ll send this information to him.
Pretty sure he’s going to have a great read. Thank you for sharing!
Hey I know this is off topic but I was wondering if
you knew of any widgets I could add to my blog that automatically
tweet my newest twitter updates. I’ve been looking for a plug-in like
this for quite some time and was hoping maybe you would have some experience with something
like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new
updates.
It’s nearly impossible to find well-informed people about
this topic, however, you seem like you know what you’re talking about!
Thanks
I just couldn’t depart your web site prior to suggesting that
I actually enjoyed the standard information an individual provide to your visitors?
Is gonna be again frequently to investigate cross-check new posts
No matter if some one searches for his necessary thing, thus he/she needs to
be available that in detail, therefore that thing is maintained over here.
Would love to constantly get updated great site! .
We are a group of volunteers and opening a new scheme in our
community. Your website offered us with valuable information to work on. You’ve done
a formidable job and our entire community will be thankful to you.
Thanks for your marvelous posting! I truly enjoyed reading it, you may be
a great author.I will make sure to bookmark your blog and will come back later on. I want to
encourage you to ultimately continue your
great posts, have a nice afternoon!
If some one needs to be updated with newest technologies
therefore he must be visit this site and be up to date
every day.
I have read so many content regarding the blogger lovers however this post is in fact a fastidious
post, keep it up.
Hi it’s me, I am also visiting this web page daily, this site is really pleasant and the
users are actually sharing good thoughts.
Every weekend i used to go to see this site,
for the reason that i want enjoyment, as this this site conations
really good funny information too.
Undeniably believe that which you said. Your favorite reason seemed to be on the
net the simplest thing to be aware of. I say to you, I definitely get annoyed while people consider worries that they just don’t know
about. You managed to hit the nail upon the top and also defined out the whole thing without
having side effect , people can take a signal. Will likely be back to get
more. Thanks
This is my first time go to see at here and i am genuinely
pleassant to read all at one place.
Today, I went to the beachfront with my kids.
I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put
the shell to her ear and screamed. There was a hermit crab inside
and it pinched her ear. She never wants to go back!
LoL I know this is completely off topic but I had to tell someone!
Highly descriptive article, I loved that bit. Will there be
a part 2?
These are actually impressive ideas in on the topic of
blogging. You have touched some nice things here.
Any way keep up wrinting.
Greetings! I’ve been reading your weblog for a long time now and finally got the courage to go ahead and give you a shout out from Houston Tx! Just wanted to tell you keep up the fantastic job!