当前位置：首页 > backend >正文

每日一题(9) 垃圾箱分布

backend 2025/5/18 1:37:32

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N（≤103）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤104）是居民点和垃圾箱候选地点之间的道路的条数；DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：

P1 P2 Dist

其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No Solution。

输入样例1：

输出样例1：

G1
2.0 3.3

输入样例2：

2 1 2 10
1 G1 9
2 G1 20

输出样例2：

No Solution

问题分析

这个问题可以分成几个步骤来解决：

构建图：根据输入的道路信息，构建一个包含所有居民点和垃圾箱候选点的无向图。

计算最短路径：使用Floyd-Warshall算法计算图中任意两点之间的最短路径。

评估候选点：对每个垃圾箱候选点，评估它到所有居民点的最短距离的最大值和平均值。

选择最佳点：根据题目要求的排序规则选择最佳的垃圾箱位置。

解题思路

Floyd-Warshall算法

Floyd-Warshall算法是一种求解多源点间最短路径的动态规划算法。时间复杂度为O(V³)，其中V是图中顶点的数量。

步骤如下：

初始化距离矩阵，对于直接相连的两点，距离为道路长度；对于不直接相连的两点，距离为无穷大。
对于每个顶点k，更新任意两点i和j之间的最短路径：

   dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

评估候选点

对每个垃圾箱候选点G，我们需要计算：

它到所有居民点的最短距离的最大值，记为minDist
它到所有居民点的平均距离，记为avgDist
检查是否有居民点到达不了或距离超过最大允许距离DS

选择最佳点

根据题目要求，我们按照以下规则排序候选点：

minDist越大越好，从所有最短距离中选最大的那个（即题目中没人想和垃圾箱做邻居）
如果minDist相同，avgDist越小越好（平均距离短为佳）
如果minDist和avgDist都相同，编号越小越好

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String[] s = bf.readLine().split(" ");int n = Integer.parseInt(s[0]);  // 居民点个数int m = Integer.parseInt(s[1]);  // 垃圾箱候选点个数int k = Integer.parseInt(s[2]);  // 道路条数int maxDist = Integer.parseInt(s[3]);  // 最大允许距离DSint[][] grid = new int[n + m + 1][n + m + 1];for (int i = 0; i < n + m + 1; i++) {Arrays.fill(grid[i], 999999999);  // 初始化为无穷大grid[i][i] = 0;  // 自己到自己的距离为0}// 构建图for (int i = 0; i < k; i++) {s = bf.readLine().split(" ");if (s[0].contains("G")) {// 垃圾桶编号顺延s[0] = String.valueOf(Integer.parseInt(s[0].substring(1)) + n);}if (s[1].contains("G")) {// 垃圾桶编号顺延s[1] = String.valueOf(Integer.parseInt(s[1].substring(1)) + n);}grid[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = Integer.parseInt(s[2]);grid[Integer.parseInt(s[1])][Integer.parseInt(s[0])] = Integer.parseInt(s[2]);}int[][] dp = Arrays.copyOf(grid, n + m + 1);// Floyd算法计算最短路径for (int l = 1; l <= n + m; l++) {for (int i = 1; i <= n + m; i++) {for (int j = 1; j <= n + m; j++) {dp[i][j] = Math.min(dp[i][l] + dp[l][j], dp[i][j]);}}}Map<String, double[]> res = new HashMap<>();// 计算每个候选点的最小距离和平均距离for (int i = n + 1; i < n + m + 1; i++) {double min = Integer.MAX_VALUE;double sum = 0;boolean valid = true;for (int j = 1; j <= n; j++) {if (dp[i][j] == 999999999 || dp[i][j] > maxDist) {valid = false;break;}sum += dp[i][j];if (dp[i][j] < min && dp[i][j] != 0) min = dp[i][j];}if (valid) {res.put("G" + (i - n), new double[]{min, sum / n});}}// 排序选择最佳候选点List<Map.Entry<String, double[]>> sortList = new ArrayList<>(res.entrySet());Collections.sort(sortList, new Comparator<Map.Entry<String, double[]>>() {@Overridepublic int compare(Map.Entry<String, double[]> o1, Map.Entry<String, double[]> o2) {// 在这些最短距离中选择较大的排在前面if (o1.getValue()[0] < o2.getValue()[0]) {return 1;} else if (o1.getValue()[0] > o2.getValue()[0]) {return -1;} else {// 平均距离选最小if (o1.getValue()[1] < o2.getValue()[1]) {return -1;} else if (o1.getValue()[1] > o2.getValue()[1]) {return 1;} else {return o1.getKey().compareTo(o2.getKey());}}}});if (res.isEmpty()) System.out.println("No Solution");else {System.out.println(sortList.get(0).getKey());double[] val = sortList.get(0).getValue();System.out.printf("%.1f %.1f", val[0], val[1]);}}
}