题目描述

前缀和+环处理。

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

即环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;
    }
}