2019 hdu多校第一场 D.Vacation

hdu 6581 Vacation

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6581

O(n）直接贴代码了

#include<bits/stdc++.h>

using namespace std;
long long s[100005],l[100005],v[100005];

int main(){
    long long n;
    long long xxx=0;
    while(scanf("%lld",&n)>0){
        xxx=0;
    for(int i=0;i<=n;i++){
        scanf("%lld",&l[i]);
        xxx+=l[i];
    }
    for(int i=0;i<=n;i++){
        scanf("%lld",&s[i]);
    }
    for(int i=0;i<=n;i++){
        scanf("%lld",&v[i]);
    }
    long long vv=v[0];
    long long ll=l[0];
    xxx-=l[0];
    double ss=s[0];
    double lucheng=0;
    double t=0;
    double sum=0;
    double ans = s[0]*1.0/v[0];
    for(int i=n;i>0;i--){
        xxx-=l[i];
        if(v[i]>vv){
            continue;
        }
        t=(ss-(s[i]+l[i]+xxx)*1.0)/(vv-v[i]);
        if(ss-vv*t>0){
            sum = t + (ss-vv*t)/v[i];
            ans=max(ans,sum);
        }
    }
    printf("%.10lf\n",ans);
    }
}