C. Discrete Acceleration(浮点二分)

Problem - 1408C - Codeforces

 题意:
 

有一条长度为l米的道路。路的起点坐标为0，路的终点坐标为l。

有两辆汽车，第一辆站在路的起点，第二辆站在路的终点。它们将同时开始行驶。第一辆车将从起点开到终点，第二辆车将从终点开到起点。

最初，他们将以每秒1米的速度行驶。在不同的坐标a1,a2,...,an有n个旗子。每当两辆汽车中的任何一辆驶过一个旗子时，该汽车的速度每秒增加1米。

求汽车相遇（到达同一坐标）需要多长时间。

输入
第一行包含一个整数t（1≤t≤104）：测试案例的数量。

每个测试案例的第一行包含两个整数n，l（1≤n≤105，1≤l≤109）：旗帜的数量和道路的长度。

第二行包含n个整数a1,a2,...,an，按递增顺序排列（1≤a1

保证所有测试案例的n之和不超过105。

输出
对于每个测试案例，打印一个单一的实数：汽车相遇所需的时间。

如果你的答案的绝对或相对误差不超过10-6，将被认为是正确的。更正式地说，如果你的答案是a，而陪审团的答案是b，如果|a-b|max(1,b)≤10-6，你的答案将被认为是正确的。

例子
输入
5
2 10
1 9
1 10
1
5 7
1 2 3 4 6
2 1000000000
413470354 982876160
9 478
1 10 25 33 239 445 453 468 477
输出
3.000000000000000
3.666666666666667
2.047619047619048
329737645.750000000000000
53.700000000000000

题解:

看到那么多小数还有求最小的基本就是浮点二分了

关键在于二分什么

我们可以二分他们相遇的地点,check他们走前半段与后半段的时间,

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
double a[100050];
int n;
double L;
double check1(double x)
{
	double pre = 0;
	double t = 0;
	double v = 1.0;
	for(int i = 1;i <= n;i++)
	{
		if(a[i] <= x)
		{
			t += (a[i] - pre)/v;
			pre = a[i];
			v += 1.0;
		}
		else
		{
			break;
		}
	}
	t += (x - pre)/v;
	return t;
}
double check2(double x)
{
	double pre = L;
	double t = 0;
	double  v = 1.0;
	for(int i = n;i >= 1;i--)
	{
		if(a[i] >= x)
		{
			t += (pre-a[i])/v;
			pre = a[i];
			v+= 1.0;
		}
		else
		{
			break;
		}
	}
	t += (pre - x)/v;
	return t;
}
void solve()
{
	cin >> n >>L;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	double l = 0,r = L;
	while(r-l > 1e-6)
	{
		double mid = (r+l)/2.0;
		double t1 = check1(mid);
		double t2 = check2(mid);
		if(t1 < t2)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	printf("%.8lf\n",check1(l));
}
int main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//
//