笔试时间：2025年10月19日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

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

输入描述

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

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

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

1 ≤ n ≤ 10⁵

1 ≤ aᵢ ≤ 10⁹

1 ≤ x, y ≤ n

输出描述

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

样例输入

3 1 2 2 2 3

样例输出

2

样例说明：

总距离 = 1+2+2 = 5

从站2到站3：顺时针距离 = 2，逆时针距离 = 3

最短距离 = min(2, 3) = 2

参考题解

解题思路：

题目要求在一个环形公路上计算两站之间的最短距离。环形意味着从x到y有两条路径：顺时针和逆时针。

关键步骤：

1. 问题转化： 环形总距离 = 所有相邻站距离之和。设顺时针距离为d1，则逆时针距离 = 总距离 - d1。最短距离 = min(d1, 总距离 - d1)
2. 处理顺时针距离： 用前缀和数组s记录从第1站到第i+1站的累计距离： s[0] = 0s[i] = a[0] + a[1] + ... + a[i-1] 这样s[v] - s[u]就是u到v的顺时针距离（当u < v时）。
3. 处理环形情况： 当u > v时（如从第3站到第2站）： 顺时针路径：先走到终点n，再从第1站走到v距离 = s[n] - s[u] + s[v]
4. 最终计算： 比较顺时针距离d1和逆时针距离(total - d1)，取较小值。

时间复杂度：O(n)

C++：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int x, y;
    cin >> x >> y;
    
    if (x == y) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<long long> s(n + 1, 0);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }
    
    long long total = s[n];
    int u = x - 1;
    int v = y - 1;
    
    long long d1 = 0;
    if (u < v) {
        d1 = s[v] - s[u];
    } else {
        d1 = s[n] - s[u] + s[v];
    }
    
    long long d2 = total - d1;
    cout << min(d1, d2) << endl;
    
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        if (x == y) {
            System.out.println(0);
            sc.close();
            return;
        }
        
        long[] s = new long[n + 1];
        s[0] = 0;
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + a[i];
        }