sách gpt4 ai đã đi

【Thuật toán】Tiền tố Tổng

In lại 作者:知者 更新时间:2024-03-13 08:49:26 27 4
mua khóa gpt4 Nike

【Thuật toán】Tiền tố Tổng

题目

先来看一道题目:(前缀和模板题)

已知一个数组A[],现在想要求出其中一些数字的和。
输入格式:
先是整数N,M,表示一共有N个数字,有M组询问
接下来有N个数,表示A[1]..A[N]的数字
接下来是M组询问,每组询问包含两个X,Y,表示想要求出A[X]..A[Y]的和

输出格式:
对于每一组询问,输出A[X]..A[Y]的和。

样例:

输入: 5 3 1 2 3 4 5 1 2 2 5 1 3 输出: 3 14 6

无脑操作

#include using namespace std; const int Max_N=100000; int N,M,A[Max_N]; int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;i++){ scanf("%d",A+i); } for(int i=1;i<=M;i++){ int X,Y; scanf("%d%d",&X,&Y); int Ans=0; for(int j=X;j<=Y;j++)Ans+=A[j]; printf("%d\n",Ans); } return 0; }

非常无脑的操作,两层循环,时间复杂度:O(N*M)
如果数据范围较大,会造成部分数据点超时,那么如何优化?

前缀和

我们可以使用预处理,在一边输入的时候就能一边计算求和,这样可以加快速度。

我们定义数组S,使得S[i]=A[1]+A[2]+...+A[i],即S[i]就是A数组前i项之和
这样写起来,一边读入就可以一边计算,代码:

for(int i=1;i<=N;i++){ scanf("%d",A+i); S[i]=S[i-1]+A[i]; }

S数组和A数组的对应关系,用样例,手算一下:

A 1 2 3 4 5 S 1 3 6 10 15

正好,S[i]就是A数组前i项之和。那么如果想要求A[X]..A[Y]的和,其实就是求:

A[X]..A[Y]
=A[1]+A[2]+...+A[X]+...+A[Y]-A[1]-A[2]-...-A[X-1]
=S[Y]-S[X-1]

前后抵消,剩余的就是A[X]..A[Y]的一部分。

这就是前缀和的基本思想。

正解

#include using namespace std; const int Max_N=100000; int N,M,A[Max_N],S[Max_N]; int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;i++){ scanf("%d",A+i);S[i]=S[i-1]+A[i]; } for(int i=1;i<=M;i++){ int X,Y; scanf("%d%d",&X,&Y); printf("%d\n",S[Y]-S[X-1]); } return 0; }
27 4 0
Bài viết được đề xuất: 【FLink】Flink 源码阅读笔记(4)- RPC
Bài viết được đề xuất: nginx代理转发url接口请求路径到spring boot后端实现真正响应
Bài viết được đề xuất: C++ 统计地铁中站名出现的字的个数
Bài viết được đề xuất: 深入理解 React 的 Virtual DOM
Giấy chứng nhận ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com