P9822 [ICPC 2020 Shanghai R] Walker

题目描述

作为一名世界闻名的旅行者，Pang 教授的研究兴趣是尽可能多地在他的一生中旅行到各个地方。

我们有一个线段 $[0,n]$。在线段上有两名旅行者。第一位旅行者位于位置 $p_1$，速度为 $v_1$（这意味着他/她每秒可以在线段上行走 $v_1$ 单位）。第二位旅行者位于位置 $p_2$，速度为 $v_2$。

从他们各自的起点开始，旅行者可以在线段上行走。他们不能走出线段。无论何时他们想要改变方向，他们可以立即转身。

请帮助 Pang 教授计算每个位置至少被一名旅行者经过所需的最短时间。

输入格式

第一行包含一个整数 $test(1\le test\le 10000)$ —— 测试用例的数量。

接下来的 $test$ 行中的第 $i$ 行包含五个数字 $n,p_{1,i},v_{1,i},p_{2,i},v_{2,i}$ ($0<n\le 10000$, $0\le p_{1,i},p_{2,i}\le n$, $0.001\le v_{1,i},v_{2,i}\le 1000$)。所有数字最多有 $3$ 位小数。

输出格式

对于每个测试用例，输出一个数字 —— 每个位置至少被一名旅行者经过所需的最短时间。

如果答案的绝对误差或相对误差不超过 $10^{-6}$，则认为答案是正确的。

输入输出样例 #1

输入 #1

2
10000.0 1.0 0.001 9999.0 0.001
4306.063 4079.874 0.607 1033.423 0.847

输出 #1

5001000.0000000000
3827.8370013755

说明/提示

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7,INF=1e9;
int T;
double n,p1,p2,v1,v2;
int main(){
    cin>>T;
    while(T--){
    	cin>>n>>p1>>v1>>p2>>v2;
    	if(p1>p2){//交换
    		swap(p1,p2);
    		swap(v1,v2);
    	}
    	double ans=INF;
		ans=min(ans,min((n+min(n-p1,p1))/v1,(n+min(n-p2,p2))/v2));//第①种情况
		ans=min(ans,max((n-p1)/v1,p2/v2));//第②种情况
		double l=p1,r=p2;
		while(r-l>eps){
			double mid=(l+r)/2;
			double t1=(mid+min(mid-p1,p1))/v1;//左边
			double t2=(n-mid+min(n-p2,p2-mid))/v2;//右边
            ans=min(ans,max(t1,t2));//更新答案
			if(t1<t2)
				l=mid;
			else
				r=mid;
		}
		printf("%.10f\n",ans);
	}
    
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容