自动搬运

查看原文

来自洛谷，原作者为

	Sliarae Re:start

搬运于2025-08-24 21:17:46，当前版本为作者最后更新于2025-03-03 23:03:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先预处理 $s_i$ 表示正着从 $0$ 走到 $a_i$ 的最小代价，$p_i$ 表示倒着从 $l$ 走到 $a_i$ 的最小代价。

钦定两个人最终在第 $i$ 到第 $i + 1$ 个加速带之间相遇。那么前面的人会花费 $s_i$ 的时间，后面的人会花费 $t_{i + 1}$ 的时间。中间还有 $d = a_{i + 1} - a_i$ 的距离要两个人一起走。

此时考虑让两个人中用时小的一个先走，如果他用这个时间差将 $d$ 的路程走完了说明不合法。否则这时两个人用时相同，此时他们的速度之和可以看作 $n + 2$，在将 $\frac{d}{n + 2}$ 加到答案中即可。

时间复杂度 $O(n)$。

#include <iostream>
#include <iomanip>

using namespace std;

const int kN = 1e5 + 5;
const double Inf = 1e9;

int n;
int a[kN];
double p[kN], s[kN];

void Solve () {
	cin >> n >> a[n + 1];
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	p[0] = 0; 
	for (int i = 1; i <= n; ++i) 
		p[i] = p[i - 1] + (a[i] - a[i - 1]) * 1.0 / i;
	s[n + 1] = 0; 
	for (int i = n; i; --i)
		s[i] = s[i + 1] + (a[i + 1] - a[i]) * 1.0 / (n - i + 1);
	double ans = Inf;
	for (int i = 0; i <= n; ++i) {
		double d = a[i + 1] - a[i];
		double x = p[i], y = s[i + 1];
		if (x < y) {
			d -= (y - x) * (i + 1);
			x = y; 
		}
		else {
			d -= (x - y) * (n - i + 1);
			y = x;
		}
		if (d > 0)
			x += d / (n + 2);
		ans = min(ans, x);
	}
	cout << fixed << setprecision(12) << ans << '\n';
}

int main () {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--) Solve();
	return 0; 
}