洛谷 \(P1632\)
一、题目大意
求平面上 \(1、2⋯n\)
二、解题思路
枚举，我们假设 \(m\) 个点的最小曼哈顿距离，我们假设汇集的点是 \((x,y)\) ，则
\(x\) 必然可以选择 \(n\) 个点的横坐标中的一个， \(y\) 也可以选 \(n\) 个点的纵坐标中的一个。
所以我们枚举 \(x\) 和 \(y\)
三、\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, x[N], y[N], dist[N], ans[N];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
memset(ans, 0x3f, sizeof ans);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { // 双重循环枚举每个已知的点
int X = x[i]; // 假设最终的结果是这个X
int Y = y[j]; // 假设最终的结果是这个Y
// 计算每个点到(X,Y)的汉密尔顿距离
for (int k = 0; k < n; k++)
dist[k] = abs(x[k] - X) + abs(y[k] - Y);
// 由小到大排序
sort(dist, dist + n);
int cnt = 0;
for (int k = 0; k < n; k++) {
cnt += dist[k]; // 累加每一个限定范围的最小距离和
ans[k] = min(ans[k], cnt);
}
}
}
// 输出答案
for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
return 0;
}