首页 > 代码库 > 算法:街区最短路径问题
算法:街区最短路径问题
package practice;import java.io.BufferedInputStream;import java.util.Arrays;import java.util.Scanner;/** * <pre> * 一个街区有很多住户,街区的街道只能为东西、南北两种方向。 * * 住户只可以沿着街道行走。 * * 各个街道之间的间隔相等。 * * 用(x,y)来表示住户坐在的街区。 * * 例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。 * * 现在要建一个邮局,使得各个住户到邮局的距离之和最少。 * * 求现在这个邮局应该建在那个地方使得所有住户距离之和最小; * </pre> * * @author caiyu * @date 2014-10-23 */public class StreetPoster { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int n = cin.nextInt(); int m; int[][] points; for (int i = 0; i < n; i++) { m = cin.nextInt(); points = new int[2][m]; for (int j = 0; j < m; j++) { points[0][j] = cin.nextInt(); points[1][j] = cin.nextInt(); } Arrays.sort(points[0]); Arrays.sort(points[1]); int t = m / 2, x = points[0][t], y = points[1][t]; int sum = 0; for (int j = 0; j < m; j++) { sum += Math.abs(x - points[0][j]) + Math.abs(y - points[1][j]); } System.out.println(sum); } }}
算法:街区最短路径问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。