每日咕咚(C++)---浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）

链接：https://ac.nowcoder.com/acm/contest/7872/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

为了让每天的锻炼任务变得更加有趣，农农和林林给ZAFU的学生们制定了一个
有趣的跑步规则，内容如下：
        
         1、假定现在有N个学生在操场跑步
         2、在一开始的时候，N个学生需要排成一列，前后间距为 X，那么队列总长为 （N-1）* X

         3、处于队尾的学生会加速追赶前面的学生，在这个过程中其余学生保持平均速度 V 不变，(队尾的同学超过所有同学后，比第二名同学领先X的间距时才视为完成一次追赶，此时当前的队尾同学才开始追赶）

         当所有学生都完成一次追赶之后，锻炼结束。 
        
         现在告知每一位学生在不同位置追赶时的速度 Uij，请你帮助计算学生们完成锻炼的期望时长。 
        

            
 

输入描述:

 N X V

U11---------U1N

----------------

----------------

UN1--------UNN

1 <= N <= 500 (N为正整数)
0 < X <= 10000 (X为浮点数)
0 < V <= 1000  (V为浮点数) 
V + 1 < Uij <= 2000  (Uij为浮点数) 

输出描述:

RES （表示期望时长，保留两位小数）

示例1

输入

 

2 2.00 1.00
2.00 3.00
3.00 2.00

输出

 

6.00

说明

共有两名学生

可行的排列有

【1， 2】 此时时长为 （2.00 * 2）/ （2.00 - 1.00）+ （2.00 * 2） / （2.00 - 1.00）= 8.00

【2， 1】 此时时长为 （2.00 * 2） /（3.00 - 1.00）+ （2.00 * 2） / （3.00 - 1.00）= 4.00

期望时长为 6.00

 

 

---

 

 

当时想了好久，还是没法读懂意思...

但现在大概清楚了。

 

其实示例中的 2.00  3.00 是对于学生一而言的， 并且和其初始位置相联系，也就是如果当学生一 一开始 在第一个位置时，其追赶速度为2.00 (当学生一在队尾时，学生一的追赶速度生效，学生一的追赶速度即为 2.00，当在其余位置时 速度都为V，)；当学生一 一开始 在第2个位置时，其追赶速度为3.00 (既学生一此时就在队尾时，学生一的追赶速度即为 3.00，追赶完后变为V)。

比如题给例子，N = 2时，当【1, 2】时，注意此时 1 在一号位，也就是 1 之后的追赶速度为 2.00(当学生1在队尾时生效，当学生1不在队尾时，其速度都为V)；而 2 在二号位，其追赶速度为 2.00。
那么此时应该由2先追赶，因为学生二一开始在 2 号位，所以其追赶速度就为2.00，等到学生二已经在学生一的前面了，学生一再以2.00的追赶速度来追赶速度为V的学生二。

 

然后还有另一种组合【2， 1】，同理可得和上述类似的情况。

 

 

那么当有N个学生时，其情况如下，并且可以求得其期望时长。
也就是N个学生有 N！的排列方式，对于每种方式，每个人都会有个属于自己的初始位置，这个初始位置又和自己的追赶速度相挂钩，那么其实每个人都会有到队尾的时候，并且其跑步距离都是(N-1) * X + X = N * X。

 

这样综合来看 N！的情况，对于第一个人，他有可能初始时在第1~N个位置，假设对于他在第一个位置，后续又有(N-1)!种组合，也就说明他如果一开始在第一个位置，那么就得跑NX * (N-1)! 的距离，且其速度都为 u11,那么时间就是 NX * (N-1)! / u11

以此类推，第一个人所用的总时间t1如下：



那么全部情况所有人所用的时间为：

 

 

所以期望时长为:

 

---

 

下面代码1

#include <iostream>
#include <cstdio>
using namespace std;

double u[980][980]; //u[i][j] = x，表示第i个学生在初始位置为正数第j个时的追赶速度 

int main()
{
	int n;
	double x, v;
	scanf("%d %lf %lf",&n, &x, &v);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			scanf("%lf", &u[i][j]);
		}
	}
	
	double ans = 0;
	for(int i = 1; i <= n; i++) { //遍历每一个学生 
		for(int j = 1; j <= n; j++) { //都会进行从队尾开始跑 NX 的距离
			ans += (n * x) / (u[i][j] - v);
		}
	}
	
	printf("%.2f\n", ans / n);
	
	return 0;
}
	
	
			

代码2

#include <iostream>
#include <cstdio>
using namespace std;

double u[980][980]; //u[i][j] = x，表示第i个学生在初始位置为正数第j个时的追赶速度 

int main()
{
	int n;
	double x, v;
	scanf("%d %lf %lf",&n, &x, &v);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			scanf("%lf", &u[i][j]);
		}
	}
	
	double ans = 0;
	for(int i = 1; i <= n; i++) { //遍历每一个学生 
		for(int j = 1; j <= n; j++) { //都会进行从队尾开始跑 NX 的距离
			ans += x / (u[i][j] - v);
		}
	}
	
	printf("%.2lf\n", ans);
	
	return 0;
}