【題解】a693: 吞食天地

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a693

【方法-1】一般做法 (TLE)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        int a[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < m; i++) {
            int l, r;
            cin >> l >> r;
            l--; //改成 0-based
            r--; //改成 0-based
            int sum = 0;
            for (int j = l; j <= r; j++) {
                sum += a[j];
            }
            cout << sum << "\n";
        }
    }
    
    return 0;
}

【方法-2】前綴和

#include <iostream>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        int x, ps[n+1];
        ps[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            ps[i] = ps[i-1] + x; //前綴和
        }
        for (int i = 0; i < m; i++) {
            int l, r;
            cin >> l >> r;
            cout << ps[r] - ps[l-1] << "\n";
        }
    }
    
    return 0;
}

分享本文 Share with friends