a693 - 吞食天地

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算指定區間內食物的總飽足度。給定一個包含 n 個食物飽足度的陣列，以及 m 個查詢，每個查詢包含一個區間 [l, r]，需要計算從第 l 個食物到第 r 個食物的飽足度總和。

解題思路

本題可以使用前綴和 (Prefix Sum) 的方法來高效地計算區間和。首先，計算一個前綴和陣列 sum，其中 sum[i] 儲存了從第一個食物到第 i 個食物的飽足度總和。然後，對於每個查詢 [l, r]，可以使用 sum[r] - sum[l-1] 計算出該區間的飽足度總和。

複雜度分析

• 時間複雜度: O(n + m)，其中 n 是食物的數量，m 是查詢的數量。計算前綴和陣列需要 O(n) 的時間，處理每個查詢需要 O(1) 的時間，總共需要 O(m) 的時間。
• 空間複雜度: O(n)，需要額外儲存前綴和陣列。

程式碼

#include <stdio.h>
int main(){
	int m,n,j,k;
	while(scanf("%d%d",&n,&m)>0){
		int a[n]={0},sum[n]={0};
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			sum[i]+=a[i]+sum[i-1];
		}
		while(m--){
			scanf("%d%d",&j,&k);
			printf("%d\n",sum[k]-sum[j-1]);
		}
	}
}