[CSP-J 2022 山东] 宴会

知识点

绝对值、最值维护、代数推导

解题思路

每个人到达时间为max(ti+xi-x,ti-xi+x)。维护A=max(ti+xi)、B=max(ti-xi)，则宴会最早开始时间函数为max(A-x,B+x)，在两条直线交点x=(A-B)/2处最小。用整数保存两倍坐标；偶数输出整数，奇数输出末尾.5。

正确性说明

将所有人的两个线性项共同取最大后得到max(A-x,B+x)。前者随x递减，后者随x递增，最大值在二者相等的唯一交点达到最小，因此给出的坐标唯一最优。A≥B，因为所有xi非负，坐标非负；无需浮点二分。

易错点

输入是先给完整x数组，再给t数组；要求输出位置而不是最早时间；整数不附带.0；总n约束跨测试组。

复杂度

时间O(Σn)，本实现保存x数组使用O(max n)空间。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n;cin>>n;vector<long long>x(n);for(auto&v:x)cin>>v;long long A=LLONG_MIN,B=LLONG_MIN;for(int i=0;i<n;i++){long long t;cin>>t;A=max(A,t+x[i]);B=max(B,t-x[i]);}long long v=A-B;cout<<v/2;if(v%2)cout<<".5";cout<<'\n';}}