pat 甲级 A1046 Shortest Distance (20分)

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805435700199424

题目大意：

给出一个由N个出口构成的闭合高速公路，求出任意给定两个出口的最短距离。

输入格式：由两个部分构成，第一部分即为第一行，首先输入出口个数N（1~N表示），然后是N个整数(D1,D2,...,DN)，其中，Di表示第i个出口与第i+1个出口之间的距离，DN表示第N个出口与第1个出口之间的距离。数字之间用空格隔开。在第二部分中，首先，在第2行给出查询次数k，接着k行即为k对需要查询的出口。

输出格式：给出k对查询出口间的最短距离，分别占据k行。

思路分析：

本题较为简单，唯一值得注意的是，在输入N个出口时，预处理N个出口到出口1的距离，同时，记录下整个循环的距离dissum。便于在查询时，可达到O(1)的时间复杂度，否则将是O(N)的时间复杂度，会超时。

参考代码：

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

const int maxn=100005;
int main(){
    int sum, m, c, n, A[maxn], dis[maxn];
    dis[0] = A[0] = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){ //dis[i]表示第i个出口到第1个出口的距离，经过出口为2~i。
        scanf("%d",&A[i]);
        dis[i]=dis[i-1] + A[i-1];
        sum = dis[i];
    }
    sum += A[n]; //加上第n个出口与第1个出口间的距离，得到循环总距离。
    scanf("%d",&m);
        for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a > b) swap(a, b);
        c = dis[b]-dis[a];
        printf("%d\n",min(c, sum - c));
    }
    return 0;
}