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

· · 题解

这题绿？建议这题和原题都降橙。

题目即使 \max\limits_{i=1}^n\{|x_i-x_0|+t_i\} 尽量小。由 |a-b|=\max\{a-b,b-a\}，\max\limits_{i=1}^n\{|x_i-x_0|+t_i\}=\max\limits_{i=1}^n\{\max\{x_i-x_0,x_0-x\}+t_i\}=\max\limits_{i=1}^n\{\max\{t_i+x_i-x_0,x_0-(x_i-t_i)\}\}。

分别将 x_i+t_i，x_i-t_i 看作一个新的点，再删去 x_i 这个点，则题目即求选择一个点 x_0 使得所有点中距离该点最远的点离该点尽量近。答案为 \dfrac{\max\{x_i+t_i\}+\min\{x_i-t_i\}}{2}。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+2;
int x[N],t[N];

int main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        int mx=-1e9,mn=1e9;
        for(int i=1; i<=n; i++) cin>>x[i];
        for(int i=1; i<=n; i++) cin>>t[i];
        for(int i=1; i<=n; i++) mx=max(mx,x[i]+t[i]),mn=min(mn,x[i]-t[i]); 
        cout<<(mx+mn)/2.0<<"\n";
    }
    return 0;
}