原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：
有一个很长的彩带，有 nnn 个彩珠，它们可以被分成 kkk 组，分别坐落在彩带的不同位置上
允许：
剪一段彩带，保证这个彩带中含有所有 kkk 种珠子
求最小彩带的裁剪长度
限制：
可能存在某些坐标并没有珠子
可能存在一个坐标有多颗珠子
1.3 题目数据范围与猜测
n≤106 1≤k≤60 0≤珠子位置<231n \le 10^6~~~~~~~~~~1\le k \le 60~~~~~~~~~~0\le珠子位置<2^{31}n≤106 1≤k≤60 0≤珠子位置<231
1.4 一句话概括题意
有一个数轴，有若干珠子坐落在上，求分割最短距离使得该范围内包含所有种类的珠子
2 题目破题推导
2.1 第一步：以终为始
以终为始思考：要想使得答案最短，这个区间的样子应为？
先给一个基本猜测：至少存在一个区间，使得该区间左右端点均坐落在彩珠上且 左→右左 \rightarrow 右左→右 这个区间内包含所有种类的彩珠
2.2 第二步：数学推导+证明
假设我们有一个任意合法区间 [l0,r0][l_0,r_0][l0 ,r0 ]，l0l_0l0 和 r0r_0r0 可以是数轴上的任意实数，满足这个范围内含有全部 kkk 种彩珠
* 处理左端点
如果 l0l_0l0 本身就在某个彩珠上，记 l1←l0l_1 \leftarrow l_0l1 ←l0
如果 l0l_0l0 并不在某个彩珠上，找到其右边第一个彩珠的位置，记作 l1l_1l1
* 处理右端点
如果 r0r_0r0 本身就在某个彩珠上，记 r1←r0r_1 \leftarrow r_0r1 ←r0
如果 r0r_0r0 并不在某个彩珠上，找到其左边第一个彩珠的位置，记作 r1r_1r1
原来的彩珠范围内 [l0,r0][l_0,r_0][l0 ,r0 ] 内的所有彩珠，一定都留在 [l1,r1][l_1,r_1][l1 ,r1 ] 的范围内，因为我们只是调整了空白区域的位置
同时 r0−l0≥r1−l1r_0-l_0\ge r_1-l_1r0 −l0 ≥r1 −l1 ，所以一定保证这会比原来结果好
那么一旦存在多个结果均比原来结果好，就说明一定存在一个区间使得左右端点在彩珠上且满足截取要求
2.3 第三步：限制思维
那么我们就把一个数轴上所有实数区间变成若干个区间，这些区间是任意两个点位置的左右端点
这样有左右端点的限制了
3 模型匹配
每个点按位置从左到右排序
然后大概类似一个双指针：head和tail分别都是珠子编号
tail不断++，直到扩展区间能完全包含 kkk 种珠子，更新答案，然后收缩头部直到区间不能完全包含 kkk 种珠子
4 最终代码（禁止抄袭，仅用于参考）
