首页 > 试题广场 >

航海

[编程题]航海
  • 热度指数：655 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
二维平面的海上有只船，每只船所在位置为，每只船还有一个权值，现在他们需要聚在一起商讨捕鱼大业，他们想请你找到一个点使得该点到其他点的带权曼哈顿距离之和最小。带权曼哈顿距离=实际曼哈顿距离权值。

输出表示最小的带权输出最小的带权距离之和。

示例1

输入

2,[2,1],[1,1],[1,1]

输出

1

说明

可以选取(1,1)点，答案为1

备注:
数组下标从0开始

 

算法知识视频讲解
开通博客
头像 漫漫云天自翱翔
发表于 2021-08-13 22:28:27
题解一： 数学方法题解思路： 首先，给出结论给定N个点（x1,x2...xn），要找到使得 :最小得x; 此点比然是其中位数。证明：首先对N个点排序.假设该点在N个点中xi：如果这个点往右移xi+1两者相减，可得向右移距离变化：xi+1-x1始终大于零，所以当i<=n/2时，（2i - n）小 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Maokt
发表于 2021-08-05 22:40:15
算法思想一：暴力法 解题思路： 对于求解本题要寻找一个点使得该点到其他点的带权曼哈顿距离之和最小，自然想到遍历所有点，对于每一个点求一个带权曼哈顿距离，然后找出最小值即可。 由题值： A点到B、C两点之间的带权曼哈顿距离： 若单独计算x这一维的曼哈顿距离有： 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Tag_Kausal
发表于 2020-02-07 11:08:46
首先来看一个简化版的问题，一条线上有个点，为了把所有点移到一起，怎么移动花费最小？假设我们现在选取了一个位置，它左边及处有个点，右边有个点，现在总花费为。我们现在让右移一个单位，记为，那么很明显处的花费变成了，可以发现从左到右花费是先减少再增大的，不难得知这是一个单峰函数，且在的时候取得最值，其实这 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-08-09 14:35:37
题意整理 二维海面上有n只船，每只船有一个坐标，以及一个权值。 求最小的带权曼哈顿距离。 方法一（求极值） 1.解题思路 简要分析：首先考虑一个简化版的情况，一维横轴上有n个点，要从这个n个点中，找到一个点，使得其他点移动到这个点的距离之和最小。假设当前处于第x个点的位置（位置p），当前的最小移 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-05 16:22:13
题目描述二维平面的海上有n只船，每只船所在位置为(Xi,Yi)，每只船还有一个权值Wi，现在他们需要聚在一起商讨捕鱼大业，他们想请你找到一个点使得该点到其他点的带权曼哈顿距离之和最小。带权曼哈顿距离=实际曼哈顿距离∗权值。输出表示最小的带权输出最小的带权距离之和。 方法一：暴力解法 求解思路对于求解 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-03 17:43:31
思路： 题目的主要信息： 一共有n艘船，默认从其中选出一艘船的位置到其他所有船的带权曼哈顿距离最小。 带权曼哈顿距离公式：如果AB两点的坐标分别为，，权重分别是与，则从A到B的曼哈顿距离 = ，我们可以发现二者是分开算的，因此我们单独计算，然后相加。 方法一：暴力法具体做法：对于C点到AB两点的 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 思维 排序
难度：
1条回答 6639浏览

热门推荐

通过挑战的用户

查看代码

相关试题

航海

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号