ZYF015 圆圈舞蹈
ZYF015 圆圈舞蹈
【算法标签】 双指针、滑动窗口
【语法标签】 :数组、滑动窗口、前缀和
熊大妈的奶牛们围成一个圆圈,但是它们之间的间隔不一样。现在要找出两只奶牛之间“最远”的距离。这里的“距离”指的是:从奶牛 A 到奶牛 B,不管是顺时针走还是逆时针走,取这两条路径里较短的那一段长度。然后我们需要在所有奶牛对中,找到这样“较短路径里的最大值”。
样例输入:
5
1 2 3 4 5输出:
7我们来拆解一下这个样例:
- 首先,这 5 头奶牛围成环,每段顺时针距离分别是
d₁=1(第 0 头→第 1 头)、d₂=2(第 1 头→第 2 头)、d₃=3(第 2 头→第 3 头)、d₄=4(第 3 头→第 4 头)、d₅=5(第 4 头→第 0 头)。 - 整个环的总长度(周长)就是
1+2+3+4+5 = 15。 - 现在要找“任意两头奶牛之间,顺时针和逆时针中较短的那一段”的最大值。
我们可以枚举每一对奶牛,计算它们的“较短距离”,再取最大值。不过因为 N 可能很大(比如 1e5),暴力枚举 O(N²) 肯定会超时,所以得想更聪明的办法——但其实原理很简单:
- 对于环形结构,“A 到 B 的较短距离” = min(顺时针从 A 到 B 的长度, 总周长 − 顺时针从 A 到 B 的长度)。
- 而我们要找的是所有 (A,B) 对中,这个 min 值的最大值。
换个角度想:“较短距离的最大值” 一定不超过 周长的一半(因为如果某段的顺时针长度已经超过周长/2,那逆时针就会更短,所以较短距离不会超过周长/2)。因此,我们可以遍历每一个“起点”,计算从它开始顺时针走,最多能走多远才使得 “当前走的长度 ≤ 周长/2”,然后记录这个过程中的最大值。
拿样例来说:
总周长是 1+2+3+4+5 = 15,一半是 7.5。所以我们只需要看“从某一头开始,顺时针累加距离,直到累加和即将超过 7.5 为止,此时的累加和与剩下的(周长−累加和)取较小值,然后看哪个较大”。
具体到样例:
- 从第 0 头开始:顺时针依次是 1, 1+2=3, 3+3=6, 6+4=10(这时候已经超过 7.5 了,所以停在 6,剩下的就是 15−6=9 → 较短距离是 min(6,9)=6)。或者也可以看 “6” 对应的下一段?不,其实更直接的是,当累加到 6 时,下一头是第 3 头,此时从第 0 头到第 3 头顺时针是 6,逆时针就是 15−6=9,所以较短是 6;
- 从第 1 头开始:顺时针是 2, 2+3=5, 5+4=9(超过 7.5,停在 5,剩下 15−5=10 → 较短 min(5,10)=5);
- 从第 2 头开始:顺时针是 3, 3+4=7, 7+5=12(超过 7.5,停在 7,剩下 15−7=8 → 较短 min(7,8)=7);
- 从第 3 头开始:顺时针是 4, 4+5=9(超过 7.5,停在 4,剩下 15−4=11 → 较短 min(4,11)=4);
- 从第 4 头开始:顺时针是 5, 5+1=6, 6+2=8(超过 7.5,停在 5,剩下 15−5=10 → 较短 min(5,10)=5);
把这些较短距离列出来:6,5,7,4,5 → 其中最大的就是 7,所以输出 7。
解题思路总结
先计算整个环的总长度(周长) sum。
我们要找的是:对于每一个可能的“起点”,顺时针累加距离,直到累加和 ≤ sum/2,然后记录此时的累加和 s,以及剩下的 sum−s,取 min(s, sum−s);在这个过程中找最大的那个 min 值。
为了高效计算,我们可以用前缀和 + 双指针 或者 滑动窗口 的思想:
先计算前缀和数组 preSum,其中 preSum[i] 表示从第 0 头到第 i 头顺时针的距离(preSum[0]=0, preSum[1]=d₁, preSum[2]=d₁+d₂, ..., preSum[N]=sum)。
然后用两个指针(或一个指针 + 一个变量记录当前和),在环形结构上滑动,维护“当前连续段的和 ≤ sum/2”,并更新最大值。
不过更简单的方式是:因为是环形,我们可以把数组复制一份(变成长度 2N),然后用滑动窗口在 [0, 2N) 上找长度不超过 N 的窗口,且窗口和 ≤ sum/2,同时记录最大的窗口和。这样就能在 O(N) 时间内解决问题。
