题目链接: https://www.luogu.com.cn/problem/P1632
题目大意:
求平面上 \(1\),\(2 \cdots n\) 个点的曼哈顿距离的最小值.
解题思路:
枚举, 我们假设 \(m\) 个点的最小曼哈顿距离, 我们假设汇集的点是 \((x,y)\) , 则 \(x\) 必然可以选择 \(n\) 个点的横坐标中的一个, \(y\) 也可以选 \(n\) 个点的纵坐标中的一个.
所以我们枚举 \(x\) 和 \(y\) 然后求距离即可.
实现代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 55;
- int n, x[maxn], y[maxn], dist[maxn], ans[maxn];
- int main() {
- cin>> n;
- for (int i = 0; i <n; i ++) cin>> x[i]>> y[i];
- for (int i = 0; i <n; i ++) ans[i] = -1;
- for (int i = 0; i < n; i ++) {
- for (int j = 0; j < n; j ++) {
- int xx = x[i];
- int yy = y[j];
- for (int k = 0; k < n; k ++) {
- dist[k] = abs(x[k] - xx) + abs(y[k] - yy);
- }
- sort(dist, dist+n);
- int cnt = 0;
- for (int k = 0; k < n; k ++) {
- cnt += dist[k];
- if (ans[k] == -1 || ans[k]> cnt) ans[k] = cnt;
- }
- }
- }
- for (int i = 0; i < n; i ++)
- printf("%d\n", ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3399544.html