解题思路

• 将公路视为一个有 n 个站点的环，给出顺时针相邻两站的距离数组 a[1..n]（其中 a[n] 为第 n 站到第 1 站的距离）。

• 要求从站点 x 到 y 的最短路程。显然只有两种走法：

  1. 顺时针从较小编号走到较大编号的区间和；
  2. 逆时针，其距离为“环总长 − 上述区间和”。

• 因此先计算区间和 segment = sum(a[min(x,y)] .. a[max(x,y)-1]) 与总和 total = sum(a[1..n])，答案为 min(segment, total - segment)。

• 相关算法：前缀和/区间求和（此处直接一次线性求和即可）。

复杂度分析

• 计算总和与区间和各遍历一次（或一次遍历同时得到），时间复杂度 O(n)。
• 仅使用若干整型变量，空间复杂度 O(1)。
• 注意使用 64 位整型以避免距离和溢出。

代码实现

Python

# -*- coding: utf-8 -*-

import sys

def min_ring_distance(n, arr, x, y):
    # 若相同站点，距离为0
    if x == y:
        return 0
    if x > y:
        x, y = y, x
    total = sum(arr)  # 环总长
    # 顺时针区间和：从站 x 到站 y 之间，包含边 (x->x+1 ... y-1->y)
    seg = sum(arr[x-1:y-1])
    return min(seg, total - seg)

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    arr = [int(next(it)) for _ in range(n)]
    x = int(next(it)); y = int(next(it))
    ans = min_ring_distance(n, arr, x, y)
    print(ans)

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名为 Main
// 说明：使用自定义快速输入以适配 n 可达 1e5 的数据规模
import java.io.*;
import java.util.*;

public class Main {

    // 计算最短距离的函数
    static long minRingDistance(int n, long[] a, int x, int y) {
        if (x == y) return 0L;
        if (x > y) { int t = x; x = y; y = t; }
        long total = 0L;
        for (int i = 0; i < n; i++) total += a[i]; // 环总长
        long seg = 0L;
        for (int i = x - 1; i <= y - 2; i++) seg += a[i]; // 顺时针区间和
        return Math.min(seg, total - seg);
    }

    // 简单高效的输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= 32);
            long sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong();
        int x = fs.nextInt();
        int y = fs.nextInt();
        long ans = minRingDistance(n, a, x, y);
        System.out.println(ans);
    }
}

C++

// ACM 风格，主函数中完成输入输出
#include <bits/stdc++.h>
using namespace std;

// 计算最短距离的函数
long long min_ring_distance(int n, const vector<long long>& a, int x, int y) {
    if (x == y) return 0LL;
    if (x > y) swap(x, y);
    long long total = 0, seg = 0;
    for (int i = 0; i < n; ++i) total += a[i];        // 环总长
    for (int i = x - 1; i <= y - 2; ++i) seg += a[i]; // 顺时针区间和
    return min(seg, total - seg);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int x, y; 
    cin >> x >> y;

    cout << min_ring_distance(n, a, x, y) << "\n";
    return 0;
}

题目内容

有一个环形的公路，上面共有 $n$ 站，现在给定了顺时针第站到第 $i+1$ 站之间的距离(特殊的，也给出了第 $n$ 站到第 $1$ 站的距离)。小美想沿着公路第 $x$ 站走到第 $y$ 站，她想知道最短的距离是多少?

输入描述

第一行输入一个正整数 $n$ ，代表站的数量.

第二行输入 $n$ 个正整数,前 $n-1$ 个数代表顺时针沿着公路走， $i$ 站到第 $i+1$ 站之间的距离;最后一个正整数代表顺时针沿着公路走，第 $n$ 站到第 $1$ 站的距离。

第三行输入两个正整数 $x$ 和 $y$ ,代表小美的出发地和目的地。

$1≤n≤10^5$

$1≤a_i≤10^9$

$1≤x,y≤n$

输出描述

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

样例1

输入

3
1 2 2
2 3

输出

2

样例2

输入

3
1 2 2
1 3

输出

2