[PAT-A] 1046 Shortest Distance

Java

测试点2超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]);
        int[] dist = new int[n + 1];
        int[] sum = new int[n + 1];
        int circle = 0;

        for (int i = 1; i <= n; i++) {
            dist[i] = Integer.parseInt(first[i]);
            sum[i] = sum[i - 1] + dist[i];
            circle += dist[i];
        }

        int m = Integer.parseInt(reader.readLine());
        for (int i = 0; i < m; i++) {
            String[] line = reader.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);
            int low = Math.min(start, end);
            int high = Math.max(start, end);

            int delta = sum[high - 1] - sum[low - 1];
            System.out.println(Math.min(delta, circle - (delta)));
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int s[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);

        int l1 = abs(s[a - 1] - s[b - 1]);
        int l2 = abs(s[n] - l1);

        printf("%d\n", min(l1, l2));
    }

    return 0;
}