首页 / 算法 / 【推导】【数学期望】【冒泡排序】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem C. Earthquake
【推导】【数学期望】【冒泡排序】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem C. Earthquake
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【推导】【数学期望】【冒泡排序】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem C. Earthquake，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1709字，纯文字阅读大概需要3分钟。
内容图文
题意：两地之间有n条不相交路径，第i条路径由a[i]座桥组成，每座桥有一个损坏概率，让你确定一个对所有桥的检测顺序，使得检测所需的总期望次数最小。
首先，显然检测的时候，是一条路径一条路径地检测，跳跃地检测没有意义。考虑已经排好的某个路径的顺序，相邻的两条路径j和j+1如果满足：
(route[j].A+route[j].B)+(route[j+1].A+route[j+1].B)*(1.0-route[j].c)>
(route[j].A+route[j].B)*(1.0-route[j+1].c)+(route[j+1].A+route[j+1].B)
就交换它们的顺序使得答案变得更优。
用类似冒泡的方法扫n次即可。
A是routej的全部桥良好的期望检查次数，即所有桥好的概率之积乘以桥的数量。B是routej坏的情况下的期望检测次数，相当于对每座桥损坏概率从大到小排序，然后对每个桥k，其前面k-1个桥全好，它坏的概率，乘上k，然后对这个值求和。c是所有桥好的概率之积，即这个路径好的概率。
最后输出答案的时候，对所有路径求个其前面的所有路径都坏的概率*（A+B）之和即可。
#include<cstdio>
#include<algorithm>
using namespace std;
struct data{
double A,B,c;
}bridge[1005];
int n,x[1005];
int y[1005];
bool cmp(const int &a,const int &b){
return a>b;
}
int main(){
//freopen("c.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&x[i]);
double nowhao=1.0;
double huaiall=0;
for(int j=1;j<=x[i];++j){
scanf("%d",&y[j]);
}
sort(y+1,y+x[i]+1);
for(int j=1;j<=x[i];++j){
huaiall+=(double)j*nowhao*(1.0-(double)y[j]/1000.0);
nowhao*=((double)y[j]/1000.0);
}
bridge[i].A=nowhao*(double)x[i];
bridge[i].B=huaiall;
bridge[i].c=nowhao;
}
for(int i=1;i<=n;++i){
for(int j=1;j<n;++j){
if((bridge[j].A+bridge[j].B)+(bridge[j+1].A+bridge[j+1].B)*(1.0-bridge[j].c)>
(bridge[j].A+bridge[j].B)*(1.0-bridge[j+1].c)+(bridge[j+1].A+bridge[j+1].B)){
swap(bridge[j],bridge[j+1]);
}
}
}
double ans=0;
double now=1.0;
double sum=0;
for(int i=1;i<=n;++i){
ans+=now*(bridge[i].A+bridge[i].B);
now*=(1.0-bridge[i].c);
}
printf("%.10f\n",ans);
return 0;
}
原文：https://www.cnblogs.com/autsky-jadek/p/8975500.html
内容总结
以上是互联网集市为您收集整理的【推导】【数学期望】【冒泡排序】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem C. Earthquake全部内容，希望文章能够帮你解决【推导】【数学期望】【冒泡排序】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem C. Earthquake所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。