题解

思路

把每台空调所在格子的初始值设为其温度，其余格子为无穷大。来自左侧空调的最优值沿位置向右每步增加 1，来自右侧空调同理向左传播。

做法

建立数组 answer 并写入所有空调温度。先从左到右扫描，用 answer[i-1]+1 松弛 answer[i]；再从右到左扫描，用 answer[i+1]+1 松弛 answer[i]。最后输出数组。

正确性证明

左向右扫描结束后，归纳可知 answer[i] 等于所有位置不超过 $i$ 的空调对格子 $i$ 的最小贡献：新位置要么使用自身源值，要么由前一格最优左侧源再增加单位距离。右向左扫描以同理加入所有右侧空调贡献。每台空调必在目标格子左侧或右侧，因此两次扫描后的最小值恰为题目公式中的全体最小值。

复杂度分析

每组测试时间复杂度为 $O(n+k)$，空间复杂度为 $O(n)$。

子任务说明

• $n\le50$ 时逐格枚举所有空调。
• 每组只有一台空调时直接计算单个 V 形函数。
• 满数据使用双向线性松弛。