给定一个整数数组 a 和公差 t,每次可以选取连续三个元素组成一个抽检组,要求这三个元素的最大值与最小值之差不超过 t,且任意两个抽检组不能共用元素。求最多能选出多少个合格抽检组。
考察候选人对贪心策略的正确性证明以及区间调度类问题的理解。
31
一条测试台上有 n 个卡槽排成一行,编号从 1 到 n。调试员一开始站在第 1 号卡槽,要把探针移到第 k 号卡槽。每次可以把探针从当前卡槽跳到任意另一个卡槽,但不能跳到 [1, n] 之外。一次移动的步长是两卡槽编号差的绝对值。监测系统会记下步长落在闭区间 [x, y] 内的移动;步长严格小于 x 或严格大于 y 时不会被记录。调试员只做不会被记录的移动。可以证明当 x ≥ 2 时他一定能到达第 k 号卡槽。求最少需要多少次移动。