c - c中曼哈顿度量的最小距离总和
问题描述
我需要有关我的代码的帮助。我有 R*S 网格和 N 个点。在每一点上都有一些人。我需要在网格中找到所有输入点的人的最小步数总和。距离以曼哈顿度量标准计算。行从 0 到 R-1 编号,列从 0 到 S-1 编号。在第一行我有 R、S 和 N,在 N 后面的行上是 N 个点的坐标和位于这些点上的人数。如果存在更多具有相同步数的点,则只需写一个。该算法找到中位数,但它可能不是正确的答案。请你能给我一些算法,给我正确的答案吗?输入示例:
5 5 3
1 1 4
4 3 3
2 4 1
输出示例:
2 2
我写了这段代码,但它不起作用。你能帮我修一下吗?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cmp(const void *a, const void *b) {
return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b);
}
int main(void) {
int N, n, i, count, rx, ry, R, S;
scanf("%d %d %d", &R, &S, &N);
int a[N][2];
int b[N][2];
long int sum = 0;
for (i = 0; i < N; i++) {
scanf("%d %d %d", &a[i][0], &b[i][0], &a[i][1]);
b[i][1] = a[i][1];
sum = sum + a[i][1];
}
n = sizeof a / sizeof *a;
qsort(a, n, sizeof *a, cmp);
if (sum % 2 == 1) {
count = (sum + 1) / 2;
for (i = 0; i < N; i++) {
count = count - a[i][1];
if (count == 0) {
rx = a[i][0];
break;
}
if (count < 0) {
rx = a[i-1][0];
break;
}
}
}
if (sum % 2 == 0) {
count = sum / 2;
for (i = 0; i < N; i++) {
count = count - a[i][1];
if (count == 0) {
rx = (int)round((a[i][0] + a[i][0]) / 2);
break;
}
if (count < 0) {
rx = a[i][0];
break;
}
}
}
if (sum % 2 == 1) {
count = (sum + 1) / 2;
for (i = 0; i < N; i++) {
count = count - b[i][1];
if (count == 0) {
ry = b[i][0];
break;
}
if (count < 0) {
ry = b[i - 1][0];
break;
}
}
}
if (sum % 2 == 0) {
count = sum / 2;
for (i = 0; i < N; i++) {
count = count - b[i][1];
if (count == 0) {
ry = (int)round((b[i][0] + b[i][0]) / 2);
break;
}
if (count < 0) {
ry = b[i][0];
break;
}
}
}
printf("%d %d", rx, ry);
return 0;
}
解决方案
我不明白你的方法,有多个问题:
- 您应该检查的返回值
scanf()
以避免无效输入的未定义行为。 - 您应该检查尺寸以避免潜在的未定义行为
- 你的距离计算似乎不正确
- 你的平价测试
sum
似乎不相关。
我会首先尝试一种蛮力方法:
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int N, R, S, i, row, col, best_row, best_col;
struct { int row, col, count; } *points;
long int sum, best_sum;
if (scanf("%d %d %d", &R, &S, &N) != 3 || R < 0 || S < 0 || N < 0) {
printf("invalid input\n");
return 1;
}
points = calloc(N, sizeof *points);
if (points == NULL) {
printf("allocation failure\n");
return 1;
}
for (i = 0; i < N; i++) {
if (scanf("%d %d %d", &points[i].row, &points[i].col, &points[i].count) != 3) {
printf("invalid input\n");
return 1;
}
}
best_row = best_col = -1;
best_sum = LONG_MAX;
for (row = 0; row < R; row++) {
for (col = 0; col < S; col++) {
sum = 0;
for (i = 0; i < N; i++) {
sum += points[i].count * (abs(row - points[i].row) + abs(col - points[i].col));
}
if (best_sum > sum) {
best_sum = sum;
best_row = row;
best_col = col;
}
}
}
printf("%d %d\n", best_row, best_col);
free(points);
return 0;
}
测试输入的输出:
1 1
时间复杂度是可怕的,但对于小样本集来说并不重要。您可以通过分别计算水平距离和垂直距离的总和来降低复杂性。
推荐阅读
- javascript - 我如何在 ReactJS 上比较和连接两个数组
- ios - 如何根据点击的单元格更改数组
- ios - iOS N 如何获取所有用户代理字符串
- python - 在 Keras 中导入 Attention 包会出现 ModuleNotFoundError: No module named 'attention'
- xcode11 - 当项目包含资产目录时,Xcode 11-beta3 构建失败:错误:未知参数“--development-region”
- docker - NTLM Kerberos 支持在 nginx 服务器后面设置的身份服务器(不适用于 IE)
- python - 网络抓取 pubmeds 2., 3., 4... 页面
- .net - IIS 上的 SystemBadImageFormat 异常
- sql - 从 varchar 字段结果中删除数字和括号
- python - 无法安装旧版本的python