牛牛的魔法卡

[编程题]牛牛的魔法卡

X轴上有n个点，每个点都对应有数值，你可以从任意点出发，求经过K个不同数值点的最小花费。

在两点移动的花费为两点间的距离。

如果无法经过K个不同数值点，输出 “-1”.

第一行输入两个整数 n,k,
接下来有n行，每行两个数x，y 分别表示属于数值和坐标

示例1

输入

7,3,[[0,1],[0,2],[1,5],[1,1],[0,7],[2,8],[1,3]]

坐标点5出发，经过7、8两个点就经过了3个不同的数值。
所需代价 （7-5）+（8-7） = 3

其中 1<=n<=10^6, 1<=k<=50
0<=x<k, 0<=y<=1e9

算法知识视频讲解

Peterliang

发表于 2021-10-12 10:12:21

NC562 题解 | #牛牛的魔法卡# 题意分析在一个一维坐标轴上面给出若干个位置，每个位置有一个数字，两个位置的距离就是这两个位置的差值。可以从任意一点出发，问恰好经过k个不同的数值的最短的距离是多少？思路分析我们先分析思路，我们发现，为了使经过的距离尽可能短，我们应该选择的是一段区间展开全文

changed.

发表于 2021-09-30 20:53:23

题意整理：题目给出n个坐标可能重复的点，每个点都带有一个数值，两个点之间的距离既为其坐标间的差值，要求求出从任意点出发，经过k个不同数值点的最小开销。方法一：排序+枚举起点（超时）核心思想：很容易想到的一个思路就是枚举起点然后向后遍历到满足k个不同的数值点。首先将点按其坐标进行排序，然后将展开全文

摸鱼学大师

发表于 2021-08-12 16:03:44

思路：题目的主要信息：数轴上有n个点，每个点有自己的坐标和数值从任意点出发，求经过K个不同数值点的最小花费方法一：暴力法（超时）具体做法：对排序后的坐标点，每个点都可以作为一个区间的起点，我们遍历所有起点，往后遍历，找到后续区间是否有k个不同数值的点（使用哈希表，哈希表key值记录坐标上展开全文

二分

难度：

4条回答 4收藏 2370浏览

查看代码