洛谷P8772 [蓝桥杯 2022 省 A] 求和（前缀和差分）

#include <stdio.h>
#include<stdlib.h>
int main() {
    int n;
    scanf("%d", &n);

    // 读取数组 a
    int* a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 计算前缀和数组 prefix_sum
    long long *prefix_sum=(long long*)malloc((n+1)*sizeof(long long));
    prefix_sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + a[i - 1];
    }

    // 计算答案 S
    long long S = 0;
    for (int i = 0; i < n; i++) {
        S += a[i] * (prefix_sum[n] - prefix_sum[i + 1]);
    }

    printf("%lld\n", S);
    free(a);
    free(prefix_sum);
    return 0;
}

ps：

1.虽然运行出了结果但后台一直报错，原因就是少开辟了一个空间

还有一处地方是我粗心(long long*)没写*号

2.然后有关前缀和不理解的，可以把它想象成乘法的结合律

• prefix_sum[0] = 0
• prefix_sum[1] = prefix_sum[0] + a[0] = 0 + 1 = 1
• prefix_sum[2] = prefix_sum[1] + a[1] = 1 + 3 = 4
• prefix_sum[3] = prefix_sum[2] + a[2] = 4 + 6 = 10
• prefix_sum[4] = prefix_sum[3] + a[3] = 10 + 9 = 19
• 然后题目所求可以前缀和与该数相乘可以理解为1*（19-1）+3*（19-4）+6*（19-10）+9*（19-19）=117