1 条题解
-
0
/* 注意: f[i] 表示 楼层i "能够有人在" 所花的时间, lift[i].t表示 电梯i "能够有人在" 所花的时间,以后 楼层x 能够有人在(通过电梯i)只需要lift[i].t +等待电梯出现的时间 想通: 1、想省时间,乘坐电梯只能往下。 2、电梯每下一层时间为0,最后再加n-1(减少状态方程的复杂性) 3、电梯j 让 楼层i 有人是不需要等待电梯出现的时间的( "人出电梯" 不需要等待电梯出现的时间) 4、楼层i 让 电梯j 有人是需要等待电梯出现的时间的,且再加上之前让 楼层i "能够有人在" 的时间( "人进电梯" 需要等待电梯出现的时间) 过程: 1、从上到下枚举每一层,在当前 楼层i 只有一件事情就是让第i层能够有人在的最少时间f[i]: 第i层的地板对着所有听得到的电梯说:哪个电梯有人在啊?快来更新我的f[i] 2、然后用这个最小的f[i],更新让(其他)电梯j"能够有人在"所花的最少时间lift[j].t */ #include <bits/stdc++.h> using namespace std; struct node { int st,ed; double t; node(){t=999999999.0;} }lift[210]; double ET(int a,int b)//计算等待电梯出现的时间 { return (a*(a+1)+b*(b+1))/2.0/(a+b+1); } double f[11100]; int main() { int m,n;scanf("%d%d",&m,&n); for(int i=1;i<=m;i++)scanf("%d%d",&lift[i].st,&lift[i].ed); for(int i=0;i<n;i++)f[i]=999999999.0;f[n]=0; for(int i=n;i>=1;i--) { for(int j=1;j<=m;j++) //解决f[i](不再改),即让第i层 "能够有人在" 所花的时间 { if(lift[j].st<=i && i<=lift[j].ed) f[i]=min(f[i], lift[j].t); } for(int j=1;j<=m;j++) //解决lift[j]的t,即让lift[j] "能够有人在" 所花的时间 { if(lift[j].st<=i && i<=lift[j].ed) lift[j].t=min(lift[j].t,f[i]+ET(i-lift[j].st,lift[j].ed-i)); } } printf("%.5lf\n",f[1]+n-1); return 0; }
- 1
信息
- ID
- 248
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 59
- 已通过
- 33
- 上传者