【入门】计算能力

编程基础 • 2024-12-21 20:21 • 阅读 8

描述

小蓝同学有着很强的计算能力，张老师为了检验小蓝同学的计算能力，写了一个n个数的数列。
张老师问了小蓝同学 m 个问题，每个问题都是请小蓝同学计算这个数列从第x个数开始到第y个数结束这个区间的所有数的和。
请你编程计算出结果。

输入描述

第一行包含两个整数n和m。
第二行包含n个整数。
接下来m行，每行包含两个整数x和y表示。

输出描述

共m行，每行输出一个询问的结果。

用例输入 1

6 3 1 3 6 5 4 2 1 3 2 5 3 6

用例输出 1

10 18 17

提示

【数据范围】
1≤x≤y≤n
1≤n,m≤
−1000≤数列中素的值≤1000

来源

前缀和差分

代码:

#include<iostream> using namespace std; const int N = ; int l, r; int a[N], s[N]; int main() { int n, m; cin >> n >> m; // 输入数列长度 n 和问题个数 m for(int i = 1; i <= n; i++) { cin >> a[i]; // 输入数列的第 i 个数 } s[1] = a[1]; // 计算前缀和，第一个前缀和就是第一个数本身 for(int i = 2; i <= n; i++) { s[i] = s[i - 1] + a[i]; // 计算前缀和数组，第 i 个前缀和等于前 i 个数的和 } for(int i = 1; i <= m; i++) { cin >> l >> r; // 输入每个问题的区间起点 l 和区间终点 r cout << s[r] - s[l - 1] << endl; // 输出区间 [l, r] 内所有数的和，利用前缀和数组的性质 } return 0; }

解析:

这段代码实现了输入一个数列，计算其前缀和，然后对给定的m个区间求和并输出。算法思想是利用前缀和数组来快速计算任意区间内的数的和，通过在前缀和数组中保存每个位置前所有数的和，可在O(1)的时间内求得区间和。

今天的文章【入门】计算能力分享到此就结束了，感谢您的阅读。

【入门】计算能力

相关推荐