切胡萝卜（困难版）题解

思路

对每个 $a_i$，可选结果构成集合

$$S_i=\{\lfloor a_i/p\rfloor\mid 1\le p\le k\}.$$

题目等价于从每个集合中选一个数，使所有选中数覆盖区间的长度最小。

做法

子任务 1

枚举全部 $k^n$ 个数组 $p$，直接计算每种选择的最大值与最小值。复杂度为 $O(nk^n)$。

子任务 2

枚举最终区间的下端点 $x$。对每个 $a_i$，应选择最大的合法分母，使商仍不小于 $x$：

$$p_i=\min\left(k,\left\lfloor\frac{a_i}{x}\right\rfloor\right)$$

其中 $x=0$ 时直接取 $p_i=k$。由此得到该下端点对应的最小上端点。枚举 $0\le x\le a_1$，复杂度为 $O(na_1)$。

满分算法

每个集合 $S_i$ 按升序看作一条有序序列。先令 $p_i=k$，即每条序列都指向最小值 $\lfloor a_i/k\rfloor$，并维护当前指针值的最大值。随后不断推进当前最小值所在的全部序列。

若当前商为 $v=\lfloor a_i/p_i\rfloor$，下一个更大的不同商所用的最大分母为

$$p'_i=\min\left(p_i-1,\left\lfloor\frac{a_i}{v+1}\right\rfloor\right).$$

商值不超过 $10^5$。用以商值为下标的桶、链式表头以及每个元素的当前分母，就能在 $O(1)$ 时间移动一次指针，不需要为每个元素保存全部不同商。

正确性证明

对固定下端点 $x$，任何可行选择都必须令每个商至少为 $x$。选择满足该条件的最大分母会使对应商最小，因此子任务二计算出的上端点是所有下端点不小于 $x$ 的方案中最小的。

满分算法是有序集合最小覆盖区间的标准多指针过程。当前所有指针的最小值为 $x$、最大值为 $y$ 时，区间 $[x,y]$ 是一个合法候选。若希望得到左端点严格大于 $x$ 的候选，所有当前值等于 $x$ 的序列都必须推进；不推进其中任意一条都无法提高全局最小值。公式给出的 $p'_i$ 是产生严格更大商的最大分母，所以推进后恰到达该序列的下一个不同值，没有跳过候选。当某条序列无法继续推进时，任何更大的左端点都不再可能覆盖该序列，算法可以结束。因此算法检查了所有可能成为最优解的覆盖区间，取到的最小长度即为答案。

复杂度

整数除法序列 $\lfloor a_i/p\rfloor$ 只有 $O(\sqrt{a_i})$ 个不同值。总时间复杂度为 $O(\sum_i\sqrt{a_i})$，空间复杂度为 $O(n+\max a_i)$。