列表

详情


NC13949. River

描述

在你面前有n条河,这n条河一条接着一条,并且相邻两条河之间的距离可以忽略不计。这些河都是从南往北流的。现在你站在最西边的河边,你想要游到最东边。第i条河的流速为v[i] m/s,宽w[i] m。你游泳的速度是u m/s。现在你一共有t秒的时间游泳。请问你最远能游到距离出发点多远的地方?注意你一定要游过所有的河。

输入描述

第一行三个整数n,u,t表示河的数量,游泳的速度和时间。 接下来n行,每行两个整数w[i], v[i]表示河的宽度和流速。

输出描述

如果游不过所有的河,输出-1。 否则输出两行。 第一行表示你能游到离出发点多远的地方。 第二行n个数,每个数字通过空格隔开,结尾无空格,表示每条河你游的时间。 要求保留三位小数。

示例1

输入:

2 1 6
1 1
2 1

输出:

11.591
2.000 4.000

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 9ms, 内存消耗: 496K, 提交时间: 2021-05-20 15:07:06

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
int n,u,t,w[55],v[55];
ld ans[55];
bool judge(ld x){
    ld res=0;
    for(int i=1;i<=n;i++){
        ans[i]=sqrt(((x-v[i])*(x-v[i])*w[i]*w[i])/(u*u*((x-v[i])*(x-v[i])-u*u)));
        res+=ans[i];
    }
    return res<=t;
}
int main(){
    ld x=0,y=0,L=0,R=1e9;
    scanf("%d%d%d",&n,&u,&t);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
        x+=w[i];
        L=max(L,(ld)v[i]+u);
    }
    if(u*t<x)puts("-1");
    else{
        for(int i=1;i<=100;i++){
            ld mid=(L+R)*0.5;
            if(!judge(mid))L=mid;
            else R=mid;
        }
        for(int i=1;i<=n;i++)
            y+=sqrt(ans[i]*ans[i]*u*u-w[i]*w[i])+v[i]*ans[i];
        printf("%.3Lf\n",sqrt(x*x+y*y));
        for(int i=1;i<n;i++)
            printf("%.3Lf ",ans[i]);
        printf("%.3Lf\n",ans[n]);
    }
    return 0;
}

上一题