题解：AT_abc419_c [ABC419C] King's Summit

· · 题解

先统计所有点行、列坐标的极值，取行列极值的两个中间候选位置。

计算各候选的最大距离并取最小值，最终结果为行、列最优解的最大值，以此最小化最大切比雪夫距离，得到汇聚最小时间。

看不懂？没关系，插入代码！


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> R(N), C(N);
    // 读取所有人的坐标
    for (int i = 0; i < N; ++i) {
        cin >> R[i] >> C[i];
    }
    // 找到所有行坐标的最小值和最大值
    int minR = *min_element(R.begin(), R.end());
    int maxR = *max_element(R.begin(), R.end());
    // 找到所有列坐标的最小值和最大值
    int minC = *min_element(C.begin(), C.end());
    int maxC = *max_element(C.begin(), C.end());
    // 计算行坐标的两个候选中心点（向下取整和向上取整）
    int sR_min = (minR + maxR) / 2;  // 中心点下限
    int sR_max = (minR + maxR + 1) / 2;  // 中心点上限
    // 计算列坐标的两个候选中心点
    int sC_min = (minC + maxC) / 2;  // 中心点下限
    int sC_max = (minC + maxC + 1) / 2;  // 中心点上限
    // 计算行方向的最小时间：分别计算两个候选中心点所需的最大距离，然后取较小值
    int timeR = max(maxR - sR_min, sR_min - minR);
    timeR = min(timeR, max(maxR - sR_max, sR_max - minR));
    // 计算列方向的最小时间：同样计算两个候选中心点所需的最大距离，取较小值
    int timeC = max(maxC - sC_min, sC_min - minC);
    timeC = min(timeC, max(maxC - sC_max, sC_max - minC));
    // 最终结果取行和列方向所需时间的最大值
    int r = max(timeR, timeC);
    cout << r << endl;
    return 0;
}
拔出代码！这下懂了吧？