本文共 1880 字，大约阅读时间需要 6 分钟。

The task is really simple: given $N$ exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer $N$ (in [3,$10^5$]), followed by $N$ integer distances $D_1{D}_2\cdots D_N$, where $D_i$ is the distance between the $i$-th and the ($i$+1)-st exits, and DN​ is between the $N$-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer $M$ (≤$10^4$), with $M$ lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to $N$. It is guaranteed that the total round trip distance is no more than $10^7$.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 931 32 54 1

Sample Output:

3107

思路：路径为环形，可以顺时针也可以逆时针，两种路径长度之和为环周长，故第二种路径长度=总长度-第一种路径长度，且两者最小值为最短路径。所以我们只需求固定的一种路径就行（这里求的是标号从小到大的路径）。如果直接是把两点之间的长度放入数组，然后再累计求和，遇到数据比较多的情况下会超时。这里采用的方法是前缀和。即读入数据时同时用一个数组记录从1号点到其他所有点的距离，可以降低算法复杂度

#include 
   
    #include 
    
     using namespace std;int a[100000], d[100000];//全局变量数组声明时默认元素全为0int main() {
       int n;    while (scanf("%d", &n) != EOF) {
   //codeup上是多点测试        int sum = 0;        for (int i = 1; i <= n; i++) {
               scanf("%d", &a[i]);            sum += a[i];            d[i + 1] = sum;//记录从第一个点到第i+1个点之间的距离        }        int m;        scanf("%d", &m);        while (m--) {
               int x, y;            scanf("%d%d", &x, &y);            if (x > y) {
                   swap(x, y);            }            int dis = d[y] - d[x];//            printf("%d\n", min(dis, sum - dis));        }    }    return 0;}
    
   

转载地址：https://blog.csdn.net/zxc0074869/article/details/115247673 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！