2152 越野比赛
大约 1 分钟
2152 越野比赛
【算法】 前缀和
【C++】 一维数组、前缀和
【难度】 入门
一、题目简述
个任务点(),给出相邻任务点间的距离(共 个)。 次询问(),每次问两个任务点之间的总距离。距离可能很大()。
二、解题思路
设 dist[i] 为第 个任务点到第 个任务点的距离。则任务点 到 ()的距离 = dist[a] + dist[a+1] + ... + dist[b-1]。
用前缀和:pre[i] = 从任务点 1 到任务点 的距离(即前 段距离之和)。则 到 的距离 = pre[b-1] - pre[a-1]。
注意:距离可能达 ,,前缀和可能达 ,用 long long。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
long long pre[N]; // pre[i] = 起点到任务点i+1的距离
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n - 1; i++) {
int d;
scanf("%d", &d);
pre[i] = pre[i - 1] + d;
}
while (k--) {
int a, b;
scanf("%d%d", &a, &b);
// a到b的距离 = 第a段到第b-1段之和
printf("%lld ", pre[b - 1] - pre[a - 1]);
}
printf("\n");
return 0;
}四、复杂度分析
- 时间:
- 空间:
