学步园

题目大意：一个人从（０，０）点出发，要到达（１００×ｎ，Ｄ）这个点。二维平面被分成了平行于ｘ轴的ｎ份，每一份的宽度都是ｎ，每一份的材料不一样导致在每一份当中的速度不一样。求能到达终点的最短时间。

思路：拉格朗日乘法＋二分。

思路来源 http://blog.csdn.net/iamzky/article/details/38150235

#define Double long double

Double s[maxn];
int v[maxn];
const int d=100;
int n;
Double cal(Double t){
    Double res=0;
    Double tmp=0;
    for(int i=0;i<n;i++){
        tmp=t*t/(Double)4.0*v[i]*v[i];
        s[i]=(Double)sqrt(tmp+d*d);
        res+=(Double)sqrt(tmp);
    }
    return res;
}
Double sol(){
    int dd;
    scanf("%d%d",&n,&dd);
    memset(v,0,sizeof(v));
    memset(s,0,sizeof(s));
    for(int i=0;i<n;i++){
        scanf("%d",&v[i]);
    }
    Double l=0,r=inf;
    Double mid;
    while(l<r-eps){
        mid=(l+r)/2;
        if(cal(mid)>dd){
            r=mid;
        }
        else l=mid;
    }
    Double ans=0;
    for(int i=0;i<n;i++)
        ans+=s[i]*1.0/(v[i]*1.0);
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++){
        Double ans=sol();
        printf("Case %d: %.10lf\n",tt,(double)ans);
    }
    return 0;
}

这个问题也没有解决。。哪路大神路过帮着看一下

最新wa代码。

#define eps 1e-15
Double s[maxn];
int v[maxn];
int vv[maxn];
const int d=100;
int n;
void sol(){
    int dd;
    scanf("%d%d",&n,&dd);
    memset(v,0,sizeof(v));
    memset(s,0,sizeof(s));
    memset(vv,0,sizeof(vv));
    for(int i=0;i<n;i++){
        scanf("%d",&v[i]);
        vv[i]=v[i]*v[i];
    }
    Double l=0,r=100000.0;
    Double mid;
    Double ans;
    while(l<r-eps){
        mid=(l+r)/2;
        ans=0.0;
        for(int i=0;i<n;i++)
            ans+=(Double)sqrt(mid/4.0*vv[i]);
        if(ans>dd){
            r=mid;
        }
        else l=mid;
    }
    ans=0;
    for(int i=0;i<n;i++)
        ans+=(Double)sqrt(mid/4.0*vv[i]+d*d)*1.0/(v[i]);
    printf("%.10lf\n",(double)ans);
}

int main(){
    int T;
  
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++){
        printf("Case %d: ",tt);
        sol();
    }
    return 0;
}