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

· · 题解

容易证明，宴会的开始时间为：

\max_{i}\{|x_i - x_0| + t_i\}.

我们不妨设定开始时间为 T，那么：

\begin{aligned} \forall 1 \le i \le n, |x_i - x_0| \le T - t_i &\Rightarrow x_0 \in \Big[x_i - (T - t_i), x_i + (T - t_i)\Big] \\ &\Rightarrow x_0 \in \bigcap_{i = 1} ^ n \Big[x_i - (T - t_i), x_i + (T - t_i)\Big] \\ &\Rightarrow x_0 \in \Big[\max_{i}(x_i + t_i) - T, \min_{i}(x_i - t_i) + T\Big] \\ &\Rightarrow T = \frac{\max_{i}(x_i + t_i) - \min_{i}(x_i - t_i)}{2}. \end{aligned}

此时将 T 带入原式：

\begin{aligned} x_0 &= \max_{i}(x_i + t_i) - T \\ &= \frac{\max_{i}(x_i + t_i) + \min_{i}(x_i - t_i)}{2}. \end{aligned}

时间复杂度 O(n)。

代码如下：

int main() {
#if MULTI_TEST == 1
    LL T;
    std::cin >> T;
    while (T--) {
        // Test cases...
        auto Solve = [&]() -> void {
            int n;
            std::cin >> n;
            VLL x(n + 1, 0), t(n + 1, 0);
            for (int i = 1; i <= n; ++i)
                std::cin >> x[i];
            for (int i = 1; i <= n; ++i)
                std::cin >> t[i];
            LL a = -1e18, b = 1e18;
            for (int i = 1; i <= n; ++i) {
                cmax(a, x[i] + t[i]);
                cmin(b, x[i] - t[i]);
            }
            double x_0 = (a + b) / 2.0;
            if (fabs(x_0 - round(x_0)) < 1e-9)
                std::cout << (LL)round(x_0) << "\n";
            else
                std::cout << std::fixed << std::setprecision(1) << x_0 << "\n";
            };
        Solve();
    }
#else
#endif
    return 0;
}