自动搬运

查看原文

来自洛谷，原作者为

	wangyang168 坚持不懈，力争上游

搬运于2025-08-24 23:17:09，当前版本为作者最后更新于2025-05-31 17:54:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

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

• $1 \leq K \leq 3$
• $K \leq N \leq 50$
• $0 \leq X_i \leq 100,000$
• $0 \leq Y_i \leq 100,000$

这其中最好的消息就是 $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;
}