UVA - 12230 Crossing Rivers（期望）

UVA - 12230 Crossing Rivers（期望）

You live in a village but work in another village. You decided to follow the straight path between your house (A) and the working place (B), but there are several rivers you need to cross. Assume B is to the right of A, and all the rivers lie between them. Fortunately, there is one “automatic” boat moving smoothly in each river. When you arrive the left bank of a river, just wait for the boat, then go with it. You’re so slim that carrying you does not change the speed of any boat. Days and days after, you came up with the following question: assume each boat is independently placed at random at time 0, what is the expected time to reach B from A? Your walking speed is always 1. To be more precise, for a river of length L, the distance of the boat (which could be regarded as a mathematical point) to the left bank at time 0 is uniformly chosen from interval [0, L], and the boat is equally like to be moving left or right, if it’s not precisely at the river bank. Input There will be at most 10 test cases. Each case begins with two integers n and D, where n (0 ≤ n ≤ 10) is the number of rivers between A and B, D (1 ≤ D ≤ 1000) is the distance from A to B. Each of the following n lines describes a river with 3 integers: p, L and v (0 ≤ p < D, 0 < L ≤ D, 1 ≤ v ≤ 100). p is the distance from A to the left bank of this river, L is the length of this river, v is the speed of the boat on this river. It is guaranteed that rivers lie between A and B, and they don’t overlap. The last test case is followed by n = D = 0, which should not be processed. Output For each test case, print the case number and the expected time, rounded to 3 digits after the decimal point. Print a blank line after the output of each test case. Sample Input 1 1 0 1 2 0 1 0 0 Sample Output Case 1: 1.000 Case 2: 1.000

题目大概： 有个人去目的地，路途中有n条河，总距离d，在陆地上默认速度为1，给出n条河的其实坐标S和河的宽度L，以及船速V。船在河中不断往返，人到达岸边时，船的位置是随机的。问人到达目的地的期望时间。

思路：

根据期望的线性性质解题。

由于船的位置随机，所以人过一条河的期望时间是2*L/V

由于陆地速度为1，人在陆地上的期望时间就是陆地的距离。

把路上的所有情况的期望相加就行了

代码：

#include using namespace std;int main(){ int n,d; int ans=1; while(~scanf("%d%d",&n,&d)&&(n+d)) { double sum_1=0; double sum_2=0; for(int i=1;i<=n;i++) { double u,l,v; scanf("%lf%lf%lf",&u,&l,&v); sum_1+=2*l/v; sum_2+=l; } double t=d-sum_2; t+=sum_1; printf("Case %d: %.3lf\n",ans++,t); puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。