[蓝桥杯] 求和

题目链接

               P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷

题目理解

        这道题就是公式题，我们模拟出公式后，输出最终结果即可。

        本题不难，相信很多同学第一次见到这道题都是直接暴力解题。 两个for循环，测试样例，直接拿下。

#include<bits/stdc++.h>
main()
{int n;scanf("%d",&n);int arr[n];long long sum=0;for(int i=0;i<n;i++){scanf("%d",&arr[i]);}for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){sum+=arr[i]*arr[j];}}printf("%lld",sum);
}

        不出意外的话……应该要出意外了。 

         当数据过多时，我们如果用两个for循环暴力解题，时间会超限。因此我们需要用到前缀和算法。

解题思路

        前缀和算法：前缀和是指一个数组某下标之前（包括该下标）的所有数组元素的和。通过预先计算前缀和数组，可以在后续查询数组任意区间和时，利用前缀和数组在常数时间内得出结果，从而减少重复计算，提高算法效率。

        看下面的公式能帮助我们更好的理解代码：

        完整代码 

#include<bits/stdc++.h>
// 主函数，程序的入口
// 注意：在标准 C 语言中，main 函数应显式声明返回类型为 int，这里虽可运行但不规范
int main()
{// 定义变量 n 用于存储输入整数的个数int n;// 从标准输入读取整数 nscanf("%d", &n);// s 为前缀和数组，s[i] 表示 a 数组中前 i 个数字之和// 定义两个长度为 n+1 的 long long 类型数组 a 和 s，并初始化为 0// 这里数组长度为 n+1 是为了方便处理，让数组下标从 1 开始long long a[n + 1] = {0}, s[n + 1] = {0};// 定义变量 sum 用于存储最终的计算结果，初始化为 0long long sum = 0;// 循环读取 n 个整数，并存储到数组 a 中for (int i = 1; i <= n; i++){// 从标准输入读取一个整数，并存储到数组 a 的第 i 个位置// 注意：这里使用 %d 读取，实际 a 是 long long 类型，建议使用 %lld 更规范scanf("%d", &a[i]);}// 计算前缀和数组 sfor (int i = 1; i <= n; i++){// 根据前缀和的定义，s[i] 等于 s[i-1] 加上 a[i]s[i] = s[i - 1] + a[i];}// 计算两两相乘再相加的和for (int i = 1; i <= n; i++){// s[n] 表示 a 数组中所有元素的和，s[i] 表示 a 数组中前 i 个元素的和// s[n] - s[i] 表示 a 数组中从第 i+1 个元素到第 n 个元素的和// a[i] * (s[n] - s[i]) 表示 a[i] 与后面所有元素相乘的和// 将其累加到 sum 中sum += a[i] * (s[n] - s[i]);}// 输出最终结果printf("%lld", sum);return 0;
}

拿下！ 

 

---

———（如有问题，欢迎评论区提问）———