HackMD
a693: 吞食天地
題目：
好餓歐歐歐歐
有 n 個食物在你面前排成一排
每個食物有它的飽足度
你想知道把其中一段通通吃掉會獲得多少飽足度
測資說明：
多組測資以 EOF 結束
每組測資開始有兩個正整數 n,m (n,m <= 100000)
接下來一行有 n 個不超過一千的正整數依序代表每個食物的飽足度
接下來 m 行每行有兩個數字 l,r (1 <= l <= r <= n)
代表你想要吃掉第 l 個到第 r 個食物
對每組測資輸出 m 行，代表總飽足度
C++ Code：
使用前綴和避免TLE
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n = 0, m = 0, I = 0, r = 0, tmp = 0;
while (cin >> n >> m) {
vector<int> v_food(1, 0);
vector<int> v_prefix_sum(1, 0);//前綴和
for (int i = 1; i <= n; i++) {
cin >> tmp;
v_food.push_back(tmp);
v_prefix_sum.push_back(v_prefix_sum[i - 1] + tmp);
}
for (int i = 0; i < m; i++) {
cin >> I >> r;
cout << v_prefix_sum[r] - v_prefix_sum[I - 1] << endl;
}
}
return 0;
}
