【深進1.例1】求區間和
題目描述
給定 $n$ 個正整陣列成的數列 $a_1, a_2, \cdots, a_n$ 和 $m$ 個區間 $[l_i,r_i]$，分別求這 $m$ 個區間的區間和，
輸入格式
共 $n+m+2$ 行，
第一行，為一個正整數 $n$ ，
第二行，為 $n$ 個正整數 $a_1,a_2, \cdots ,a_n$
第三行，為一個正整數 $m$ ，
第 $4$ 到第 $n+m+2$ 行，每行為兩個正整數 $l_i,r_i$ ，滿足 $1\le l_i\le r_i\le n$
輸出格式
共 $m$ 行，
第 $i$ 行為第 $i$ 組答案的詢問，
樣例 #1
樣例輸入 #1
4
4 3 2 1
2
1 4
2 3
樣例輸出 #1
10
5
提示
樣例解釋：第 1 到第 4 個數加起來和為 10，第 2 個數到第 3 個數加起來和為 5，
對于 50% 的資料：$n,m\le 1000$ ；
對于 100% 的資料：$1 \leq n,m\le 10^5$，$1 \leq a_i\le 10^4$，
對于 50% 的資料，雙重回圈暴力列舉，
#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[100010];
int l,r;
long long ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++){
l=0;
r=0;
ans=0;
cin>>l>>r;
for(int j=l;j<=r;j++)
ans+=a[j];
cout<<ans<<endl;
}
return 0;
}
對于100%的資料：使用前綴和求解
#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[100010],s[100010];
int l,r;
long long ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
ans=0;
cin>>l>>r;
ans=s[r]-s[l-1];
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545029.html
標籤：其他
上一篇：我有一篇Java Stream使用手冊，學了就是你的了！
下一篇：Pytest初識