P11854 [CSP-J 2022 山东] 宴会 题解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
const int mod = 998244353;
int x[N], t[N];
signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> x[i];
        for (int i = 1; i <= n; ++i) cin >> t[i];
        double l = 0, r = 1e9;
        for (int i = 0; i < 400; ++i) {
            double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
            double c1 = 0, c2 = 0;
            for (int j = 1; j <= n; ++j) c1 = max(c1, abs(m1 - x[j]) + t[j]);
            for (int j = 1; j <= n; ++j) c2 = max(c2, abs(m2 - x[j]) + t[j]);
            if (c1 > c2) l = m1; else r = m2;
        }
        if (abs(l - round(l)) < 1e-9) cout << fixed << setprecision(0) << l << '\n';
        else cout << fixed << setprecision(1) << l << '\n';
    }
    return 0;
}