原题链接
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 最终代码(禁止抄袭,仅用于参考)