首页 > ACM题库 > HDU-杭电 > HDU 3232-Crossing Rivers[解题报告]HOJ
2014
03-09

HDU 3232-Crossing Rivers[解题报告]HOJ

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.

输入:

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.

输出:

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.

样例输入:

1 1
0 1 2
0 1
0 0

样例输出:

Case 1: 1.000

Case 2: 1.000

#include <iostream>
#include<cstdio>
#include<cstring>

using namespace std;
int n,d;
int main()
{
 int t=1;
 while(scanf("%d%d",&n,&d)&&d)
 {

 double sum = 0.0;
 if(n==0)
 {
 double ans = (double)d;
 printf("Case %d: %.3lf\n\n",t++,ans);
 }
 else
 {
 double ans=0.0;
 double br = 0.0;
 int p,L,v;
 while(n--)
 {
 scanf("%d%d%d",&p,&L,&v);
 ans+=(double)L*2.0/(double)v;
 br+=(double)L;

 }
 ans+=(double)d-br;
 printf("Case %d: %.3lf\n\n",t++,ans);
 }
 }
 return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。