1046 Shortest Distance （20 point

1046 Shortest Distance

很直线条的写法，然而测试点3 tle😩😩😩

#include <stdio.h>
#include <algorithm>
#define N 100001
#define M 10001
using namespace std;
int main() {
    int n, len[N], sum = 0, nres, res[M][2];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &len[i]);
        sum += len[i];
    }
    scanf("%d", &nres);
    for (int i = 0; i < nres; i++)
        scanf("%d%d", &res[i][0], &res[i][1]);
    for (int i = 0; i < nres; i++) {
        int dis = 0;
        int low=min(res[i][0],res[i][1]),high=max(res[i][0],res[i][1]);
        for (int j = low; j < high; ++j) {
            dis+=len[j];
        }
        printf("%d\n",min(dis,sum-dis));
    }
    return 0;
}

记忆化一下？

#include <stdio.h>
#include <algorithm>

#define N 100010
#define M 10010
using namespace std;

int main() {
    int n, sum[N], total = 0, nres, res[M][2], ii;
    sum[0] = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &ii);
        sum[i] += sum[i - 1] + ii;
        total += ii;
    }
    scanf("%d", &nres);
    for (int i = 0; i < nres; i++) {
        scanf("%d%d", &res[i][0], &res[i][1]);
        int dis = 0;
        int low = min(res[i][0], res[i][1]), high = max(res[i][0], res[i][1]);
        dis = sum[high - 1] - sum[low - 1];
        printf("%d\n", min(dis, total - dis));
    }
    return 0;
}

AC了。。。