打卡信奥刷题（2269）用C++实现信奥 P13374 [GCJ 2011 #2] Airport Walkways

题目摘要：在机场走廊上，你需要从起点移动到终点X米处。走廊上有若干自动步道，每条步道有不同的速度w_i。你的步行速度为S，奔跑速度为R，最多可奔跑t秒。步道不会重叠但可连续排列。求合理安排步行/奔跑时的最短到达时间。输入包含多组测试数据，每组给出走廊长度、速度参数、步道信息。输出最短时间，精度要求10^-6。样例展示了不同情况下的最优解。数据范围包括T≤40，X≤10^6，N≤1000等。

rogeliu

911人浏览 · 2025-10-22 13:43:14

rogeliu · 2025-10-22 13:43:14 发布

P13374 [GCJ 2011 #2] Airport Walkways

题目描述

你现在在机场，站在 $0$ 点。通往登机口的走廊长度为 $X$ 米，你的飞机即将起飞。走廊上有若干条自动步道，每条步道的速度为 $w_i$ 。当你在步道上行走或奔跑时，你的速度为（你的速度 $+$ $w_i$ ）。步道不会移动它们的位置，只是让你移动得更快。步道之间不会重叠：在走廊的任意一点，至多只有一条步道，但一条步道可以在另一条步道结束的地方开始。

你的正常步行速度为 $S$ 。你担心可能赶不上飞机，因此你可以选择奔跑一段时间——你最多可以以速度 $R$ 奔跑 $t$ 秒。你不需要连续奔跑 $t$ 秒：你可以将这 $t$ 秒分成任意多个时间段，甚至可以不用完全部时间。

请问，在你合理安排步行和奔跑的情况下，最短需要多少时间才能到达登机口 $X$ 点？

输入格式

输入的第一行是测试用例数 $T$ 。接下来有 $T$ 组测试数据。每组测试数据的第一行为五个整数： $X$ （走廊长度，单位为米）、 $S$ （步行速度，单位为米/秒）、 $R$ （奔跑速度，单位为米/秒）、 $t$ （最大奔跑时间，单位为秒）、 $N$ （步道数量）。

接下来的 $N$ 行，每行包含三个整数： $B_i$ 、 $E_i$ 和 $w_i$ ，分别表示第 $i$ 条步道的起点、终点（距离起点的米数）以及步道的速度（单位为米/秒）。

输出格式

对于每组测试数据，输出一行，格式为 “Case # $x$ : $y$ ”，其中 $x$ 是测试编号（从 $1$ 开始）， $y$ 是你到达 $X$ 点所需的最短时间（单位为秒）。当且仅当你的答案的相对或绝对误差不超过 $10^{-6}$ 时，才会被判为正确。

输入输出样例 #1

输入 #1

3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

输出 #1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

说明/提示

样例解释

在第一个样例中，最优的做法是立即开始奔跑，并奔跑 1 秒。

数据范围

$\leq T \leq 40$ 。
$\leq S < R \leq 100$ 。
$\leq w_i \leq 100$ 。
$\leq B_i < E_i \leq X$ 。
$Ei≤Bi+1E_i \leq B_{i+1}$ 。

小数据集（8 分，测试集 1 - 可见）

$\leq t \leq 100$ 。
$\leq X \leq 100$ 。
$\leq N \leq 20$ 。
时间限制：3 秒。

大数据集（10 分，测试集 2 - 隐藏）

$\leq t \leq 10^6$ 。
$\leq X \leq 10^6$ 。
$\leq N \leq 1000$ 。
时间限制：6 秒。

由 ChatGPT 4.1 翻译

C++实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
struct line{ //存步道的结构体
	double lon,v;
}l[N];
int T,n;
double x,s,r,t,b,e,w;
double suml,sumt,vrun,lesst,uset;
bool cmp(line a,line b){
	return a.v<b.v;
}
signed main(){
	scanf("%lld",&T);
	for(int step=1;step<=T;step++){
		scanf("%lf%lf%lf%lf%lld",&x,&s,&r,&t,&n);
		suml=0,sumt=0,lesst=0;
		for(int i=1;i<=n;i++){
			scanf("%lf%lf%lf",&b,&e,&w);
			l[i].lon=e-b;
			l[i].v=s+w;
			suml+=l[i].lon;
		}
		if(x>suml){
			l[n+1].lon=x-suml;
			l[n+1].v=s;
			n++;
		}
		for(int i=1;i<=n;i++) sumt+=l[i].lon/l[i].v;
		sort(l+1,l+1+n,cmp);
		for(int i=1;i<=n;i++){
			if(t<=0) break;
			vrun=l[i].v-s+r;
			uset=min(t,l[i].lon/vrun);
			lesst+=uset*(r-s)/l[i].v;
			t-=uset;
		}
		printf("Case #%lld: %lf\n",step,sumt-lesst);
	}
	return 0;
}