给定一个环形数组,询问数组中第x位置与第y位置的最小距离。
因为是环形数组,所以可以顺时针走或是逆时针走,题目只有一组询问,并且n也不大,所以直接模拟即可。时间复杂度为O(N)。
如果涉及到了多组询问,可以用前缀和的方式进行优化。
定义:pre[i]表示前i个数的和
在一个环形公园步道上,均匀分布着 n 个观景点,编号为 1 到 n。步道是一个闭合的环,从第 n 个观景点可以沿着顺时针走回第 1 个观景点。
相邻观景点之间沿顺时针方向的距离已知,第 i 个距离表示从观景点 i 到观景点 i+1(当 i=n 时,为从 n 到 1)的路径长度。
现在你需要计算从观景点 x 到观景点 y 的最短路径长度。你可以选择顺时针或逆时针方向移动。
数据范围如下:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.