题解：P11854 [CSP-J2022 山东] 宴会

· · 题解

题意

给定长度为 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;
}