A27691. 赛车游戏 (car.cpp)
填空题
中等
知识点
题目描述
赛车游戏 (car.cpp)
题目描述
陶陶和天天喜欢玩赛车游戏，在游戏中有一条直赛道长度为 L ，陶陶的赛车在起点为 0的位置，准备向终点行驶，天天的赛车在终点为 L 的位置，准备向起点行驶。赛车的初始速度都为 1，在赛道上有n个加速带，第 i 加速带的位置为ai ，当小车经过一个加速带时，它的速度就增加 1，请你帮忙计算出两车相遇时间。
输入格式
第一行仅有一个整数 T表示测试数据的组数，每组测试数据的第一行包含两个整数n 和 L，第二行包含 n 个整数 a1,a2,a3,...,an。
输出格式
共有T行，每行仅有一个数，依次对应每组测试数据的答案，表示两车相遇的时间。允许误差不超过10-6
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
int a[N];
int n, m;
bool judge(double t)
{
int s1 = 1; double t1 = t, index1 = 0;
for(int i = 1; i <= n; ++i)
{
if(index1 >= m) return 1;
double temp = (a[i] - index1) / s1; //跑到下个点需要的时间
if(t1 >= temp) t1 -= temp, index1 = a[i], s1++;
else break;
}
index1 += t1 * s1;
int s2 = 1; double t2 = t, index2 = m;
for(int i = n; i >= 1; --i)
{
if(index2 <= index1) return 1;
double temp = (index2 - a[i]) / s2;
if(t2 >= temp) t2 -= temp, s2++, index2 = a[i];
else break;
}
index2 -= t2 * s2;
return index2 <= index1;
}
int main()
{
int t; cin >> t;
while(t--)
{
scanf("%d %d", &n, &m);
for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
double l = 0, r = 1E10;
while(r - l > 1E-6)
{
double mid = (l + r) / 2;
if(judge(mid)) r = mid;
else l = mid;
}
printf("%.8f\n", l);
}
return 0;
}
上一题
下一题