首页 > 代码库 > Codeforces 700A As Fast As Possible（二分答案）
Codeforces 700A As Fast As Possible（二分答案）
【题目链接】 http://codeforces.com/problemset/problem/700/A
【题目大意】
有一辆限载k人速度为v2的车，n个步行速度均为v1的人要通过一段长度为l的距离，每个人只能上车一次，车可以来回走，问所有人到达目的地所需要的最短时间是多少
【题解】
因为车可以载k个人，所以，我们把人k个为一组分成(n+k-1)/k组，记为p吗，设需要的最短时间为t，每个人在车上待的时间为t2，那么可以列方程v1*(t-t2)+v2*t2=l，我们可以发现t2可以用t来表示，又因为每次车载完一组人，回来去载下一组人是一个相遇和追逐的问题，设车折回需要时间为t3，我们可以得t2*(v2-v1)=t3*(v2+v1)，同时t2和t3以及t的关系又必须满足t2*p+t3*(p-1)<=t，解方程可以得到t，由于考虑到可能会出现精度误差的问题，因此二分答案代入检验。
【代码】
#include <cstdio>double v1,v2,l,r,m;int n,k;bool check(double t){ double t2=(m-v1*t)/(v2-v1); double t3=(v2-v1)*t2/(v2+v1); int p=(n+k-1)/k; double ans=t2*p+t3*(p-1); if(ans<=t)return 1; return 0;}int main(){ scanf("%d%lf%lf%lf%d",&n,&m,&v1,&v2,&k); l=m/v2; r=m/v1; for(int i=1;i<=10000;i++){ double mid=(l+r)/2; if(check(mid))r=mid; else l=mid; }printf("%.10f\n",r); return 0;}
Codeforces 700A As Fast As Possible（二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。