题目描述

一个环形高速公路上有 N 个出口，共有 M 次询问，每次询问你需要回答其中两个出口之间的最短距离是多少。

第一行首先包含一个整数 N，接下来包含 N 个整数 D1,D2,…,DN，其中 Di 是第 i 个出口与第 i+1 个出口之间的距离，DN 是第 N 个出口与第 1 个出口之间的距离。

第二行包含一个整数 M，表示询问次数。

接下来 M 行，每行包含两个整数，表示询问两个出口之间的最短距离。

输出格式

共 M 行，每行输出一个查询的答案。

样例

输入样例：
5 1 2 4 14 9
3
1 3
2 5
4 1
输出样例：
3
10
7

算法1

1.dis[i]表示从一号结点顺时针方向到达i号结点的下一个结点的距离（1<=i<=N）,sum表示一圈的总距离，对于每一个查询都是比较l->r的顺时针方向与逆时针方向的最短距离。
2.dis[i]类似于前缀和的思想表示的是1号结点到i的距离和加上i-1号结点的距离到i+1号的距离i
3.每次读入查询左右边界，要保证左边界始终比右边界小（即顺时方向遍历）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int sum=0;
    vector<int>dis(n+1);
    for(int i=1;i<=n;i++)
    {     int t;
         scanf("%d",&t);
          sum+=t;
          dis[i]=sum;  //前缀和的思想
    }
    int m;
    cin>>m;
  for(int i=0;i<m;i++)
    {
        int l,r;
       scanf("%d %d",&l,&r);
        if(l>r) swap(l,r);
        int temp=dis[r-1]-dis[l-1];//表示的是l->r之间的顺时针方向的距离（因为d[i]是表示一号结点到N结点的后一位的距离，所以减一才是l->r的距离）
        cout<<min(temp,sum-temp)<<endl;
    }
    return 0;
}

算法2

前缀和+环处理。

对于环的处理非常容易，只需要倍长一下数据即可。

即环1->2->3->4->5，5->1可以展开成：

1 2 3 4 5 1 2 3 4 5

从城市1到3既可以走1->2->3也可以走3->4->5->1了。

C++ 代码

include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, m, s[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> s[i], s[i + n] = s[i];
    for (int i = 1; i <= n + n; i ++) s[i] += s[i - 1];
    cin >> m;
    while (m --)
    {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        cout << min(s[b - 1] - s[a - 1], s[a + n - 1] - s[b - 1]) << endl;
    }
}