2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛--I郊游（数学题）

题目描述

2018年萌新刚升为队长，于是带领校队的n名队员一起去郊游，他选定的地点与学校的距离为l米。

为了更快达到目的地，萌新计算了经费后为大家租赁了一辆限乘k人的车，队员们都非常不满，但对于萌新队长敢怒不敢言。
现已知队员走路的速度为v₁，车的速度为v₂，每位队员只能上车一次。
你的任务是帮助萌新确定到达目的地所用的时间（保留10位小数，考虑上车下车、车掉头时间不计）

输入描述:

第一行输入一个整数m，代表m组数据。
接下来m行，输入5个正整数n，l，v1,v2,k。
其中1≤m≤1000，1≤n≤10000, 1≤l≤109, 1≤v1<v2≤109, 1≤k≤n

输出描述:

输出一行，为一个实数。代表萌新确定到达目的地所用的时间（保留10位小数，考虑上车下车、车掉头时间不计）

示例1

输入

1
3 6 1 2 1

输出

4.7142857143

数学物理不分家~~~啊哈哈哈，我就当他是物理好了

过程有一点麻烦，但是思路理清了的话 ， 就很明了啦。

首先，车和人是同时从起点出发的。求最优解的话也就是说求最短时间，车是可以随时放人下车和掉头的。

最后一批人直接坐车到终点，和他们同时到达，因为要保证时间最优。

每个人经过的流程大致是这样的 人走一段距离-->坐上车跑一段距离--->下车走到终点（包括最后坐车的）一起到达。

车不断的来回接人。

由上可以得到两个结论：

1：每一批人走的距离是一样的。2：车载每一批人行驶的距离也是一样的（理由是因为要同时到达）

设一共有p批人

对于第一批人，起点为0的位置，如果他们是在x位置下车的，那么车回头和向前走的人相遇地点在2*v1*x/(v1+v2) （这里读者自己证明），设其为y。

{

会证明的直接略过这里，不会的可以参考一下

t1  = X/v2-----车到X的时间----此时队员走到   X*v1/v2  米

队员向前走与车往回开相遇时花费的时间相同

v1*t +v2*t = X - X*v1/v2--------> t = X(v2-v1)/v2*(v1+v2)

相遇的地点为  X*v1/v2 + v1*X*（v2-v1)/v2*(v1+v2)-----化简----->

y =  2*X*v1/(v1+v2)

}

对于第二批人起点在y，根据上面的公式可知车会在2*y的位置和向前走的人相遇。

......

第p批的时候起点在(p-1)*y，因为他们是直接坐车到终点的，坐车距离是x

那么有关系式 L-(p-1)*y=x

化简得x=l*(v1 + v2) / (2.0*v1*(p - 1) + v1 + v2)

结果就为x/v2+(l-x)/v1

下面代码：

#include <stdio.h>
int main()
{
	int m, n,l,v1,v2,k,p;
	scanf("%d" , &m);
	while(m--)
	{
		scanf("%d %d %d %d %d" , &n , &l , &v1 , &v2 , &k);
		if(n%k == 0)
		{
			p = n/k;
		}
		else
		{
			p = n/k+1;
		}
		double x = (double)l*(v1+v2)/(v1+v2+2*v1*(p-1));
		double t = (double)x/v2+(l*1.0-x)/v1;
		printf("%.10f\n" , t);
	}
	return 0;
 }