锐客网

  1. 首页 > it技术 > >

【51Nod1398】等公交

小镇的公交车站里有N辆公交，标号为0,1,2，…,N-1。这个小镇的公交运作模式比较奇葩，当必须有一辆车离开车站时，系统会随机从N辆车中选择一辆车，其中任意一辆车i被选中的概率为prob[i]/100，当车i被选中后它会离开车站，并且在之后的time[i]的时间内完成它的行程并返回车站。然后系统又开始随机选N辆车之一（存在同一辆车被连续多次选中的可能）。这个车站在0时刻发出第一班车。如果你在s时刻到达车站，且一定搭乘下一班车，那么你等待的时间的期望是多少？
Input
多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=4
每组测试数据有相同的结构构成：
每组数据第一行包含两个整数N与s，即车辆总数与到达时刻，其中1<=N<=100 ,0<=s<=100000;
之后N行，每行两个整数表示车i的信息，time[i]与prob[i],其中1<=prob[i]<=100,1<=time[i]<=100000;
其中确保prob[i]之和为100.
Output
每组数据一行输出，即等待时间的期望。（四舍五入小数后保留4位数字）
Input示例
3
2 5
5 90
100 10
4 1000
1 10
2 20
3 30
4 40
5 100000
10 90
100 4
1000 3
10000 2
100000 1
Output示例
9.5000
1.1667
21148.1473
题解
dp[i]表示在i时刻去坐车刚好发车的概率。
【【51Nod1398】等公交】代码

#include #include #include #include #include #include #include #include #include #include #include #define mod 1000000007 #define ll long long #define inf 1e9 using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar(); } return x*f; } double dp[200005],pro[105]; int n,s,tim[105]; inline void solve() { memset(dp,0,sizeof(dp)); dp[0]=1; n=read(); s=read(); for (int i=1; i<=n; i++) { tim[i]=read(); scanf("%lf",&pro[i]); pro[i]/=100; } for (int i=0; ifor (int j=1; j<=n; j++) dp[i+tim[j]]+=dp[i]*pro[j]; double ans=0; for (int i=s+1; i<200005; i++) ans+=dp[i]*(i-s); printf("%.4lf\n",ans); } int main() { int Case=read(); while (Case--) solve(); return 0; }

    推荐阅读


    上一篇：STC89C52RC内部EEPROM的读写

    下一篇：爬虫|强智系统爬虫分析