自动搬运

查看原文

来自洛谷，原作者为

	TainityAnle My excellence is undeniable!

搬运于2025-08-24 23:10:50，当前版本为作者最后更新于2025-03-05 20:10:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定长度为 $n$ 的序列 $x$ 和 $t$，求出一个最小的 $x_0$，使得 $\max(t_i+|x_0-x_i|)$ 最小。

思路

这个题是大原题，CF1730B，连样例都一样。

发现无论 $x_0$ 怎么取，$t_i$ 对答案都没有影响。所以考虑把它转化一下。

如果没有 $t_i$ 的话，肯定是最左边的和最右边的中点最优。$t_i$ 可以这样转化：我们不妨考虑先把 $t_i$ 转成都往左走，取这时的最左边；再让所有人先往右走 $t_i$，取这时的最右，就可以得到答案。

因为 $x_i+t_i$ 最大的一定在最右边，$x_i-t_i$ 最小的一定在最左边，如果取最小的 $x_i-t_i$ 和最大的 $x_i+t_i$ 是正确的。

答案就是 $\dfrac{\max(x_i+t_i)+\min(x_i-t_i)}{2}$。

注意保留一位小数。

AC Code

代码很简短。

#include<bits/stdc++.h>
using namespace std;
int a[114514],n,x,T,maxx,minn;
double ans;
int main() {
	cin>>T;
	while(T--) {
		cin>>n;
		for(int i=1; i<=n; i++) cin>>a[i];
		maxx=-1000000007,minn=1000000007;
		for(int i=1; i<=n; i++) {
			cin>>x;
			maxx=max(maxx,a[i]+x);
			minn=min(minn,a[i]-x);
		}
		ans=(maxx+minn)/2.0;
		if(floor(ans)==ans) printf("%d\n",(int)ans);
		else printf("%.1f\n",ans);
	}
	return 0;
}