ZeroJudge 解題筆記：a693. 吞食天地

作者：王一哲
日期：2025年7月13日


ZeroJudge 題目連結：a693. 吞食天地

解題想法

用前綴和解題，如果要求陣列中索引值 [left, right] 的區間和，即為前綴和 psum[right] - psum[left-1]。

Python 程式碼

逐行讀取測資、輸出結果，使用時間約為 0.5 s，記憶體約為 11.8 MB，通過測試。如果改用 print 輸出答案，使用時間約為 1.2 s，記憶體約為 11.7 MB。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [0] + list(map(int, sys.stdin.readline().split()))
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, sys.stdin.readline().split())
        isum = psum[right] - psum[left-1]
        sys.stdout.write(f"{isum:d}\n")

一次讀取所有測資，最後再一次輸出所有結果，使用時間約為 0.5 s，記憶體約為 36.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    psum = [0] + list(map(int, lines[idx].split()))
    idx += 1
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, lines[idx].split())
        idx += 1
        isum = psum[right] - psum[left-1]
        result.append(f"{isum:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 62 ms，記憶體約為 312 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF) {
        int psum[n+1] = {0};
        for(int i=1; i<=n; i++) {  // 轉成前綴和
            int p; scanf("%d", &p);
            psum[i] = p + psum[i-1];
        }
        for(int i=0; i<m; i++) {  // 讀取 m 行
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%d\n", psum[right] - psum[left-1]);
        }
    }
    return 0;
}