hdu 6581 Vacation – fffasttime

多校第一场的签到题。。全场都在过就我不会。。。

正解O(n)估计出题人都没想到。。
如果把两辆车怼到一起看成一个事件，可以用堆维护，每次合并两辆车，但是比较麻烦。

然而观察会发现答案肯定是某辆车堵着后面所有车。那么只要枚举每辆车，假设它堵着后面的车，然后算一下通过时间的最大值就行了。因为如果它不堵着后面的车，那么肯定它更快通过线，比真实答案小。如果它也被前面的车堵了，那么实际速度会变慢，这样算出来也会比真实答案小。。。

```
#include <bits/stdc++.h>
```

#define rep(i,a,b) for (int i=a;i<=b;i++)

```
using namespace std;
```
```
typedef double db;
```
```
const int N=100010;
```
```
db l[N],s[N],v[N],ss[N];
```
```
int main(){
```
```
	int n,cnt=0;
```
```
	while (~scanf("%d",&n)){
```
```
		ss[0]=0;db ans=0;
```
```
		rep(i,0,n) scanf("%lf",s+i);
```
```
		rep(i,0,n) scanf("%lf",l+i);
```
```
		rep(i,0,n) scanf("%lf",v+i);
```
```
		rep(i,1,n) ss[i]=ss[i-1]+s[i];
```

		rep(i,0,n) ans=max(ans,(l[i]+ss[i])/v[i]);

```
		printf("%.10f\n",ans);
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论 取消回复

发表评论取消回复