解题思路
操作在储能舱之间转移 1 单位电量,总量守恒,目标是变成回文且次数最少。
- 可行性:偶数长度时,回文序列总和必为偶数;若 n 为偶数且 ∑c 为奇数,无解,输出 −1。奇数长度总有解。
- 配对:最终必须 ci′=cn+1−i。对每个对称对 (i,n+1−i),两端差值 ∣ci−cn+1−i∣ 需要通过转移抹平。
- 代价:每次操作使某个舱 +1、另一舱 −1,全局最少次数等于所有对称对差值和的一半(向上取整),即 ⌈2∑∣ci−cn+1−i∣⌉。奇数差额可通过中间舱或其他配对消化。
复杂度分析