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

先说一下情况,这个最终版本的答案是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;
}