专栏文章

题解：P13165 [GCJ 2017 #1B] Steed 2: Cruise Control

CCute_F
P13165题解参与者 6已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mioxmjom
此快照首次捕获于
2025/12/03 02:49
3 个月前
此快照最后确认于
2025/12/03 02:49
3 个月前
查看原文

题目大意

一共有 TT 组数据，每组数据有两个整数 DD 和 NN。NN 代表马的数量。之后给出 NN 条马目前所处的位置和它的速度，问 Annie 的马在不超过其他马的前提下，最大速度是多少。

思路分析

题目中说 Annie 和其他 NN 匹马都沿着一条单向公路向东行进。我们可以把这条单项公路看作一个数轴，Annie 最开始时位于数轴的起点，也就是 00 位置。输入的 DD 表示所有马的目的地，也就是 Annie 的终点。题目中说所有马都不会超过它前面那条马，如果追上了就会将自己的速度减至更慢的那匹马的速度。所以 Annie 既然不想超过其他的马，就一定会受最慢的那匹马的限制，那我们就需要找出最慢的那匹马的速度。这匹马既然速度最慢，那如果没有不能超过其他马的限制，它所花费的时间肯定是最多的。所以我们可以求出本来每匹马所需要花费的时间，找到最大值，最后用总路程除以时间即可。

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
double T,d,n,k[N],s[N],t[N], maxn;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	std::cin>>T;
	for(int i=1;i<=T;i++){
		std::cin>>d>>n;
		maxn=-100;
		memset(t,0,sizeof(t));//多测不清空，爆零两行泪 
		for(int j=1;j<=n;j++){
			std::cin>>k[j]>>s[j];
			t[j]=(d-k[j])/s[j];//求出花费的时间 
			maxn=max(maxn,t[j]);//找最大值 
		}
		std::cout<<"Case #"<<i<<": ";
		std::cout << fixed <<setprecision(6) << double(d)/maxn <<"\n";//求出速度 
	}
		return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...