c - c中曼哈顿度量的最小距离总和

Question

我的代码需要帮助。我有 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;
}

Answer 1

我不明白你的做法，有很多问题:

• 您应该检查 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

时间复杂度很恐怖，不过对于小样本集来说无所谓。您可以通过分别计算水平距离和垂直距离的总和来降低复杂性。