C. Discrete Acceleration(浮点二分)_资讯

C. Discrete Acceleration(浮点二分)

创始人

2024-01-22 06:54:54

0次

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
#include
#include
#include
#include
#include
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();}
}
//
//

上一篇：解读JVM级别本地缓存Caffeine青出于蓝的要诀 —— 缘何会更强、如何去上手

下一篇：everything常用搜索命令

C. Discrete Acceleration(浮点二分)

相关内容

热门资讯