Leoric
2017-09-22 15:20 南京理工大学 C++
关注
应该是曼哈顿距离吧。 将点按x升序排序，则第k个的点到其它点的x总距离=(k-1)x-sum(1~k-1) + sum(k+1~n)-(n-k)x， 其中sum( i ~ j )为i到j点的x总和（可以用O(1)的复杂度求出）。 然后将点按y升序排序，以类似方法求得每个点到其他点y的总距离。 最后从n个点里挑出x，y总距离最小的。 总时间复杂度为排序的时间复杂度O(nlogn)
查看原帖
点赞 2
相关推荐
OPPO成长空间 520人发布 
投递亚信科技（中国）有限公司等公司10个岗位 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 哪些公司开提前批了？ #
27196次浏览 267人参与
# 入职以后才知道的校招谎言 #
88562次浏览 580人参与
# 风评不好的公司，你会去吗？ #
62456次浏览 448人参与
# 华子oc时间线 #
1244432次浏览 6484人参与
# 哪些公司校招卡第一学历 #
69275次浏览 273人参与
# 校招第一份工作你干了多久？ #
95239次浏览 423人参与
# 实习如何「偷」产出？ #
52056次浏览 1343人参与
# 除了主业以外，你还有哪些其他收入？ #
12385次浏览 202人参与
# 不卡学历的大厂有哪些？ #
29982次浏览 231人参与
# 校招阶段，学历VS技术哪个更重要？ #
17984次浏览 188人参与
# 机械人，你的第一份感谢信是谁给的 #
30564次浏览 310人参与
# 职场新人体验 #
26580次浏览 249人参与
# 工作丧失热情的瞬间 #
294065次浏览 2372人参与
# 腾讯音乐求职进展汇总 #
98232次浏览 570人参与
# 社恐入职新公司如何融入团队 #
11980次浏览 63人参与
# 你的秋招第一场笔试是哪家 #
148068次浏览 1485人参与
# 校园里的破防时刻 #
11700次浏览 128人参与
# 你投递的公司有几家约面了？ #
108991次浏览 779人参与
# Offer比较，你最看重什么？ #
191701次浏览 1301人参与
# 你觉得技术面多长时间合理？ #
100327次浏览 720人参与