邮局选址问题c语言实现代码
时间: 2023-11-12 12:08:20 浏览: 55
邮局选址问题是指在一定区域内建立若干个邮局,使得所有居民到最近的邮局的距离之和最小。这个问题可以用贪心算法来解决。以下是一个简单的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 1000 // 最大居民数
#define MAXK 100 // 最大邮局数
int N, K; // 居民数和邮局数
int X[MAXN+1]; // 居民的横坐标
int Y[MAXN+1]; // 居民的纵坐标
int P[MAXK+1]; // 邮局的位置
int cost[MAXK+1][MAXN+1]; // cost[i][j]表示第i个邮局到第j个居民的距离
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
scanf("%d%d", &N, &K);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &X[i], &Y[i]);
}
for (int i = 1; i <= K; i++) {
scanf("%d", &P[i]);
}
qsort(P+1, K, sizeof(int), cmp); // 将邮局位置从小到大排序
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= N; j++) {
cost[i][j] = abs(X[j] - P[i]) + abs(Y[j]); // 计算距离
}
}
int ans = 0;
for (int j = 1; j <= N; j++) {
int minCost = cost[1][j];
for (int i = 2; i <= K; i++) {
minCost = fmin(minCost, cost[i][j]); // 找到最小距离
}
ans += minCost; // 累加距离
}
printf("%d", ans);
return 0;
}
```
该代码使用了一个二维数组`cost[i][j]`来存储第i个邮局到第j个居民的距离。在计算最小距离时,使用了标准库函数`fmin()`。