思路：模拟

给定一个环形数组，询问数组中第$x$位置与第$y$位置的最小距离。

因为是环形数组，所以可以顺时针走或是逆时针走，题目只有一组询问，并且$n$也不大，所以直接模拟即可。时间复杂度为$O(N)$。

如果涉及到了多组询问，可以用前缀和的方式进行优化。

定义：$pre[i]$表示前$i$个数的和

那么$i$到$j$的距离就是$pre[j-1]-pre[i-1]$。环形数组的话可以将数组再复制一遍，这样第$1$个数与第$n$个数就会在第$n$与$n+1$的位置首尾相接。

预处理前缀和数组的时间复杂度为$O(N)$，询问的时间复杂度为$O(1)$。

代码

C++

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn=2e5+10;
int n;
int x,y;
long long a[maxn];
long long sum=0,s=0; 

int main(){
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum+=a[i];
	}
	cin>>x>>y;
	if(x>y) swap(x,y);
	for(int i=x;i<y;++i) s+=a[i];
	cout<<min(s,sum-s);
	
	
	return 0;
}

python

n = int(input())
sum_total = 0
s = 0
a = input().strip().split(" ")

for i in range(0, n):
    a[i] = int(a[i])
    sum_total += a[i]

x, y = map(int, input().split())
if x > y:
    x, y = y, x

for i in range(x-1, y-1):
    s += a[i]

print(min(s, sum_total - s))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxn = 200010; // maxn is not used in the code
        int n = scanner.nextInt();
        int x, y;
        long[] a = new long[maxn];
        long sum = 0, s = 0;

        for (int i = 1; i <= n; ++i) {
            a[i] = scanner.nextLong();
            sum += a[i];
        }

        x = scanner.nextInt();
        y = scanner.nextInt();
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }

        for (int i = x; i < y; ++i) {
            s += a[i];
        }

        System.out.println(Math.min(s, sum - s));
    }
}

题目描述

小美所在的物流公司有一个环形仓储，一共有$n$个仓储点，小美每天要在这里面搬运货物，十分劳累。

这天，小美又要将货物从第$i$个仓储点搬运到第$j$个仓储点了，他想知道，他需要走的最短的路程是多少？

输入描述

第一行输入一个正整数$n$，代表仓储点的数量。

第二行输入$n$个正整数$a_{i}$，前$n - 1$个数代表顺时针沿着环形仓储走，第$i$个仓储点到第$i+ 1$个仓储点之间的距离:最后一个正整数代表顺时针沿着环形仓储走，第$n$个仓储点到第$1$个仓储点的距离

第三行输入两个正整数$x$和$y$，代表小美需要将货物从第$x$个仓储点搬运到第$y$个仓储点。

$1<n< 10^5$

$1 < a_i < 10^9$

$1≤x,y≤n$

输出描述

一个正整数，代表小美需要走的最短距离。

样例

输入

3
1 2 3
1 2

输出

1

样例2

输入

5
2 1 3 4 1
1 3

输出

3