环状最短路

输入样例:

5 1 2 4 14 9
3
1 3
2 5
4 1

输出样例:

3
10
7

思路分析

类似前缀和的思想，预定义一个数组pdist[i],用来存储从 1 到 i 点顺时针距离
则逆时针距离 = 环的总距离(sum) - 顺时针距离，比较哪个距离更小并进行输出
a点到b点的顺时针距离则用 pdist[b] - pdist[a]表示
输入时进行预处理，不然会超时…

C++代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010;
int n,m;
int pdist[N];
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n;
    int sum = 0;
    pdist[1] = 0; // 点1到自己距离为0
    for ( int i=1; i <= n; i++ ) {
        cin >> a[i];
        sum += a[i]; 
        pdist[i+1] = sum; // 预处理
    }
    cin >> m;
    while ( m -- ) {
       int a,b;
       cin >> a >> b;
       if ( a > b ) swap(a,b);
       if ( pdist[b] - pdist[a] < sum - (pdist[b] - pdist[a])) cout << pdist[b] - pdist[a] << endl;
       else cout << sum - (pdist[b] - pdist[a]) << endl;
   }

    return 0;


}