贪心 - Shortest Distance

本以为这是一道水题，但谁知水题也有“坑”啊！

先说一下情况，这个最终版本的答案是OK的，这是我第三遍做出来的。

1. 第一个答案是暴力加和，比如求2-5，那我就从2-5加起来，然后用sum减去此和，然后取两者的较小值。但是后面一看N最大是 ，而M最大是 ，所以最多可能产生 次操作，肯定超时。

2. 第二个答案：既然超时，那我就用空间换时间呗(真是个聪明的想法💡)，还是N的问题，最多是 ，用二维数组graph[i][j]保存i和j之间的距离，共有 个空间，必然导致空间超出。

3. 这是最终版本，用dis[]保存前i个数的和，dis[1]就是1-2的距离，dis[2]就是1-3的距离，dis[n]就是一圈的距离。然后巧妙的进行减法操作就能得到任意两点间的距离，还是用sun减去，再求两者的最小值。

// runtime: 13ms
// space: 692K
// https://pintia.cn/problem-sets/994805342720868352/problems/994805435700199424
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 100001;
int dis[MAX];

int main() {
    int n, m, sum = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &dis[i]);
        sum += dis[i];
        dis[i] = sum; // 前i个和
    } // dis[0] = 0;

    scanf("%d", &m);
    for (int j = 0; j < m; ++j) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        // dis[b-1] - dis[a-1]的解释： 比如求 2-5的距离，应该是1-5的距离dis[4]减去1-2的距离dis[1]。
        // 然后求sum减去此数的另外一个顺序的距离，取两者的最小值。
        printf("%d\n", min(dis[b - 1] - dis[a - 1], sum - dis[b - 1] + dis[a - 1]));
    }
    return 0;
}