e339 - 前綴和練習

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定陣列的前綴和陣列。前綴和陣列的每個元素是原始陣列中從第一個元素到該元素的和。

解題思路

本題的核心概念是前綴和。我們可以迭代原始陣列，並在每次迭代中將當前元素加到前一個元素的前綴和上，從而計算出當前元素的前綴和。由於題目要求輸出前綴和陣列，因此我們需要一個額外的陣列來儲存計算出的前綴和。注意，題目要求輸出的是從 B[0] 到 B[N-1] 的前綴和，而程式碼中從 B[1] 開始計算，最後再輸出 B[N-1] 的值。

複雜度分析

• 時間複雜度: O(n)，其中 n 是陣列的大小。因為我們需要迭代陣列一次來計算前綴和。
• 空間複雜度: O(n)，因為我們需要一個額外的陣列來儲存前綴和。

程式碼

#include <iostream>

using namespace std;

int main(){
	
	long long int a=0,tem=0;
	while(cin >> a){
		long long int b[a],c[a];
		for(int i=0;i<a;i++){
			cin >> b[i];
			c[i]=0;
		}
		for(int i=1;i<a;i++){
			c[i]+=c[i-1]+b[i-1];
			cout << c[i] << " ";
		}
		cout << b[a-1]+c[a-1];
		cout << endl;
	}
}