竞赛题笔记（1）

题目：https://www.luogu.com.cn/problem/P1258

整体思路：
只有当甲乙同时到达目的地时才是使用时间最短的方法，因此先求出二者到达目的地所需要的时间的表达式，以时间近似相等为判定条件；通过调整甲在中途下车的地点（使用二分法）而得出答案

二分法代码：

#include
#include
int main()
{
double s,s1,s2,v1,v2,t1,t2,p;
double a,b;
scanf("%lf%lf%lf",&s,&v1,&v2);
s1=0;//s1标记左边界
s2=s;//s2标记右边界
do
{
p=(s1+s2)/2.0;//用p作为指针
a=p/v2;//车载甲所花的时间记为a
b=(p-a*v1)/(v1+v2);//车返回遇见乙所花的时间记为b
t1=a+(s-p)/v1;//甲到达目的地所花的总时间
t2=a+b+(s-(a+b)*v1)/v2;//乙到达目的地所花的总时间
if(t1<t2)//说明车把甲载到p点后甲仍然比乙先到，说明甲在车上的时间太长
{
s2=p;把右边界移至指针p处
}
else{/说明车把甲载到p点后甲比乙后到，说明甲在车上的时间太短
s1=p;//把左边界移至p点
}
}
while(fabs(t1-t2)>1e-8);//用fabs求二者差的绝对值，因为可能会有负数的出现，记得标上cmath头文件
printf("%.6lf",t1);//按照题目要求保留六位小数
return 0;

}

萌新疑问：
1、如何证明二者同时到达目的地时所需要的的时间最短，即答案；
2、我觉得甲和乙可以通过多次上下车来缩短时间来使时间更短，但是脑袋明显不够用的说，可能是我想的太复杂了？