洛谷P1258 小车问题（题解）

https://www.luogu.org/problemnew/show/P1258（题目传送）

看题的第一眼就把题归为二分题，一直向着二分的方向走，却忽略了数学的推理。推理一番后（看了题解），发现原来如此简单。

　　由题意知，若要二人一起到达B点时耗时相同且最短，则二人走的路程、坐车的路程以及走和坐车的时间相同，并且车只能回接一次。设人走的路程为x、时间为t1，坐车的时间为t2，车返回接另一个人所用时间为t3，总共人的耗时为t，则t1=x/a，t2=(s-x)/b，t3=(s-2x)/b;

t2+t3=t=(2s-3x)/b=x/a,解得x=2as/(3a+b) 故轻松地用数学解出此题。

　　数学AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int main()
 5 {
 6     double s,a,b;
 7     cin>>s>>a>>b;
 8     double x=(2*a*s)/(3*a+b);
 9     printf("%.6lf",x/a+(s-x)/b);
10     return 0;
11 }

　　既然是个二分题，当然也可以用二分做了。我们可以二分车回接另一个人时的位置，算出若在此位置车回接，二人到终点分别的总耗时t1、t2，若t1==t2，输出答案（因为这里浮点数精度有误差，所以定义相等为差的绝对值小于一个非常小的数（这里题目要求误差小于1e-6，所以就把这个很小的数设为1e-6）），若t1>t2，使左端点等于mid，若t1<t2，则使右端点等于mid，直至有答案产生或两端点的差距小于1e-6为止。

　　二分AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 double abs(double a)
 5 {
 6     return a>=0?a:-a;
 7 }
 8 int main()
 9 {
10     double s,a,b;
11     cin>>s>>a>>b;
12     double l=0,r=s,mid=(l+r)/2;
13     double t1=mid/b+(s-mid)/a,t2=(mid-mid/b*a)/(a+b)+mid/b+(s-((mid-mid/b*a)/(a+b)+mid/b)*a)/b;
14     while(r-l>=0.0000001)
15     {
16         if(abs(t1-t2)<0.000001)
17         break;
18         else
19         {
20             if(t1>t2)
21                 l=mid;
22             else 
23                 r=mid;
24         }
25         mid=(l+r)/2;
26         t1=mid/b+(s-mid)/a,t2=(mid-mid/b*a)/(a+b)+mid/b+(s-((mid-mid/b*a)/(a+b)+mid/b)*a)/b;
27     }
28     printf("%.6lf",t1);
29     return 0;
30 }

为什么要发这么一个普及难度的题呢，因为是为了提醒以后数学与信息学的联系越来越深了