首页 > 试题广场 >

邮局选址问题

[编程题]邮局选址问题

一条直线上有居民点，邮局只能建在居民点上。给定一个有序整形数组arr，每个值表示居民点的一维坐标，再给定一个正数num，表示邮局数量。

选择num个居民点建立num个邮局，使所有的居民点到邮局的总距离最短，返回最短的总距离。

第一行有两个整数N,num。分别表示居民点的数量，要建的邮局数量。
接下来一行N个整数表示邮局的坐标。保证坐标递增

输出一个整数表示答案

示例1

输入

6 2
1 2 3 4 5 1000

第一个邮局建立在3位置，第二个邮局建立在1000位置。那么1位置到邮局的距离为2,2位置到邮局距离为1,3位置到邮局的距离为0，4位置到邮局的距离为1,5位置到邮局的距离为2,1000位置到邮局的距离为0.
这种方案下的总距离为6。

算法知识视频讲解

Hephaestus_F

发表于 2022-07-30 14:44:04

import java.util.Map; import java.util.Scanner; public class Main { private static int[][ 展开全文

数学图思维

上传者：小小

难度：

4条回答 22收藏 7086浏览

查看代码

扫一扫，把题目装进口袋