题解

思路

先将位置排序，记相邻间隙为 $D_i=A_{i+1}-A_i$。

做法

最优策略可以整理为两阶段：先选择若干个间隙，在其中点各放一次诱饵；再在道路左右端点交替放置。固定第一阶段使用 $m$ 个诱饵时，应选择最大的 $m$ 个间隙。设这些间隙之和为 $S$，则中点阶段贡献 $S/2$，并把最左、最右僵尸的位置分别向内推进 $S/2$。

记 $F=\max(A_1,L-A_N)$，$B=L-A_N+A_1$，剩余端点诱饵数为 $q=K-m$。若 $q=0$，总贡献为 $S/2$；否则第一次放在较远的端点，之后交替放置，贡献合计后总答案为 $S+F+(q-1)(B+S)$。将间隙降序排列，维护前缀和并枚举 $m=0,1,\ldots,\min(N-1,K)$ 取最大值即可。

复杂度

每组数据时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。