解题思路
本题可以转化为:在环形赛道上,寻找一段沿顺时针方向的最短连续位置区间,使得该区间内恰好包含 k 个补给点(即 k 个 '1')。这段区间的最短长度即为所有可能起点下代价的最小值。若赛道中补给点总数 m<k,则无解,输出 -1。
进一步分析,对于任意一段恰好包含 k 个 '1' 的最短区间,其左端点一定落在某个补给点上(否则可以去掉左端多余的 '0' 使区间更短),右端点也必然落在某个补给点上。因此,最优区间必定是从某个补给点开始,到顺时针方向上的第 k 个补给点结束。
具体步骤
- 遍历字符串 s,记录所有补给点(字符
'1')的索引位置,存入数组 pos。设补给点总数为 m=len(pos)。