题解：P12655 [KOI 2023 Round 1] 避难所

· · 题解

思路：

这是一道很简单的枚举题。简单在它的数据范围较小，以下为题目给出的数据范围。

这其中最好的消息就是 1 \leq K \leq 3，正是因此当输入所有数据后我们可以直接定义变量 ans 表示最终答案，判断 K 的值，从而实行不同方案。

  1. 如果 K=1，我们先套一个循环模拟选取庇护所的过程，里面定义一个变量代表选取这个房屋当庇护所时的最远路程，然后再用一个循环来计算每一个房屋到这个庇护所的距离，从而找出最远距离，更新 ans。
  2. 如果 K=2，我们需要套两个循环，分别表示两个庇护所，注意两个庇护所不能是同一个房屋，里面定义一个变量代表选取这个房屋当庇护所时的最远路程，然后再用一个循环来计算每一个房屋到距离它最近的庇护所的距离，从而找出最远距离，更新 ans。
  3. 如果 K=3，我们需要套三个循环，分别表示三个庇护所，注意不能出现多个庇护所是同一个房屋的情况，里面定义一个变量代表选取这个房屋当庇护所时的最远路程，然后再用一个循环来计算每一个房屋到距离它最近的庇护所的距离，从而找出最远距离，更新 ans。

当然我们可以在开头先定义一个距离函数计算两个房屋之间的距离，这对后面的计算有帮助，可以节省码量；在所有循环都结束之后，我们只需要输出 ans 就能通过这道题了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, k, x[55], y[55];
int dis(int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);//距离函数，对后面有帮助
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);//输入加速
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    int ans = 1e9;
    if (k == 1) {
        for (int i = 1; i <= n; i++) {
            int tmp = 0;
            for (int w = 1; w <= n; w++) 
                tmp = max(tmp, dis(i, w));
            ans = min(ans, tmp);
        }
    }
    else if (k == 2) {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                int tmp = 0;
                for (int w = 1; w <= n; w++)
                    tmp = max(tmp, min(dis(i, w), dis(j, w)));
                ans = min(ans, tmp);
        }
    }
    else {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                for (int p = j + 1; p <= n; p++) {
                    int tmp = 0;
                    for (int w = 1; w <= n; w++)
                        tmp = max(tmp, min({ dis(i, w), dis(j, w),dis(p,w) }));
                    ans = min(ans, tmp);
            }
    }
    cout << ans;
}