UVA12230 过河 Crossing Rivers 题解

· · 题解

题目大意：

长度为 d 的路径上有 n 条河，船在河上任意位置任意朝向，每种情况概率相等，求通过路径的期望时间。

分析：

对于一条长为 l，船在其上速度为 v 的河，最坏情况为船在起始位置恰好朝向对岸，需等船走一个来回，即前行 2l 后才能坐船，再走 l 到达，总时间 t1=3l/v；最好情况船正好到达，直接过河时间为 t2=l/v，在两种情况之间概率均等分布，故度过每一条河期望时间 t=2l/v。

设河流总长度为 suml，则人步行的长度为 d-suml，时间也是 d-suml。

两者加和即为全程期望时间。

Code：

#include<bits/stdc++.h>
#define ff(i,s,e) for(register int i(s);i<=e;++i)
using namespace std;
inline int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=12;
int n,d,p[N],l[N],v[N];
signed main(){
    int timi=0;
    while(1){ 
        n=read(),d=read();
        if(n==d&&d==0) return 0;
        ff(i,1,n) p[i]=read(),l[i]=read(),v[i]=read();
        double ans=0;
        int sum=0;
        ff(i,1,n) ans+=l[i]*2.0/v[i],sum+=l[i];
        ans+=d-sum;
        printf("Case %d: %.3lf\n\n",++timi,ans);
    }
    return 0;
}

求通过qwq