时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M 热度指数:165
本题知识点: 二分
算法知识视频讲解

题目描述

牛牛从小就有收集魔法卡的习惯,他最大的愿望就是能够集齐 k 种不同种类的魔法卡,现在有 n 张魔法卡,这 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]]

输出

复制
3

说明

样例一:牛牛从坐标点5出发,经过7、8两个点就收集了3张不同种类的魔法卡,达成成就。
所需代价 (7-5)+(8-7) = 3

备注:

其中 1<=n<=10^6, 1<=k<=50
0<=x<k, 0<=y<=1e9
保存并调试
  • 代码提交记录