CodeForces

CF1408C Discrete Acceleration

题目大意：

数轴的原点和位置为 (l) 的点上各有一个初始速度为1m/s的小车，在原点的小车向右开，在 (l) 位置的小车向左开.在位置0到 (l) 间有n个旗子，第i个的位置为(a_i)，当两辆小车中任意一辆经过一个旗子，它的速度就增加1m/s，求两车相遇时间。

思路：

按照题意模拟。

注意相遇问题中：速度和×相遇时间=路程

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const double eps = 1e-6;
const int N = 200010;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007; //998244353
LL powmod(LL a, LL b) { LL res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }

int n, L, a[N], pos1, pos2;
long double p1, p2, tmp_time, ans_time, sp1, sp2;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while (T--) {
		cin >> n >> L;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		p1 = 0, p2 = L; //A、B的坐标
		sp1 = sp2 = 1;
		pos1 = 1, pos2 = n; //A、B将要经过的下一个旗子的下标（不是坐标
		ans_time = 0;
		while (pos2 - pos1 >= 0) { //两人在同一段之间
			tmp_time = min((a[pos1] - p1) / sp1, (p2 - a[pos2]) / sp2);
			if ((a[pos1] - p1) / sp1 <= (p2 - a[pos2]) / sp2) {
				p1 += tmp_time * sp1;
				p2 -= tmp_time * sp2;
				pos1++;
				sp1++;
			} else {
				p1 += tmp_time * sp1;
				p2 -= tmp_time * sp2;
				pos2--;
				sp2++;
			}
			ans_time += tmp_time;
		}
		cout << fixed << setprecision(12) << ans_time + (p2 - p1) / (sp1 + sp2) << endl; //到达同一段内的时间再加上相遇需要的时间
	}
	return 0;
}