本以为这是一道水题,但谁知水题也有“坑”啊!
先说一下情况,这个最终版本的答案是OK的,这是我第三遍做出来的。
第一个答案是暴力加和,比如求2-5,那我就从2-5加起来,然后用sum减去此和,然后取两者的较小值。但是后面一看N最大是 ,而M最大是 ,所以最多可能产生 次操作,肯定超时。
第二个答案:既然超时,那我就用空间换时间呗(真是个聪明的想法💡),还是N的问题,最多是 ,用二维数组graph[i][j]保存i和j之间的距离,共有 个空间,必然导致空间超出。
这是最终版本,用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; }