c++题目描述 平面上分布了 � N 个点,每个点的坐标都是一个整数。假设将一个点( � 1 x 1 , � 1 y 1 )移动到另一个点( � 2 x 2 , � 2 y 2 )的代价为两点之间的曼哈顿距离,也就是最小代价为 ∣ � 1 − � 2 ∣ + ∣ � 1 − � 2 ∣ ∣x 1 −x 2 ∣+∣y 1 −y 2 ∣。 请求出,从平面中给定的点中,任意取出 � K ( � = 1 , 2... , � K=1,2...,N) 个点,这 � K 个点移动到同一个点上最小总代价是多少? 输入 第一行一个正整数 � N。 接下来 � N 行,每行两个正整数 � � x i 和 � � y i ,为第 � i 个点的坐标,坐标的值不超过 10 10 6 6 的非负整数。 输出 输出共 � N 行,第 � i 行为使得 � i 个点在同一位置的最少代价。
时间: 2024-04-08 20:30:32 浏览: 114
输入一个正整数,判断是不是素数(C++)
对不起,我之前给出的解决方案有误。以下是一个修正后的C++解决方案:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int N;
cin >> N;
vector<pair<int, int>> points(N); // 存储点的坐标
for (int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
points[i] = make_pair(x, y);
}
vector<long long> minCost(N, 0); // 存储每个点到其他点的最小代价
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j) {
long long cost = abs(points[i].first - points[j].first) + abs(points[i].second - points[j].second);
minCost[i] += cost;
}
}
}
for (int i = 0; i < N; i++) {
cout << minCost[i] << endl;
}
return 0;
}
```
该程序首先读取输入的点的数量N,然后依次读取每个点的坐标。接下来,使用两个嵌套循环计算每个点到其他点的曼哈顿距离,并将结果累加到minCost数组中。最后,将minCost数组中的结果输出。
注意:由于点的数量可能很大,所以计算每个点到其他点的曼哈顿距离的时间复杂度为O(N^2),可能会超出时间限制。如果输入规模较大,可以考虑优化算法。
阅读全文