广州建设行业信息网站ppt公司简介模板

题目名字 求和

题目链接

题意

输入的每个数都要两两相乘，然后再加起来，求最后总和；

思路

1. 每个数乘这个数的前缀和即可

算法一：前缀和

实现步骤

1. 先把前缀和写出来
2. 再写for循环每个数都乘以自己的前缀和；

实现步骤

1. 直接在for循环输入里面进行相乘相加的运算

代码

 #include <iostream>
using namespace std;
const int N=1e6+10;
int n,a[N];
long long int sum=0,m=0;
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];sum=sum+m*a[i];m=m+a[i];}cout<<sum<<endl;return 0;
}

时间复杂度

总结

1. 在刚开始写的时候想的是用枚举的方法，两重for循环，但是只能对两个而且还超时了，所以一直写不出来，因为超时原因，所以不能直接暴力解决，可以进行一个小的运算；
2. 不把这个题想的太死板，换个解题思路，直接就是这个数和这个数的前一项的前缀和直接相乘，就会清晰明了的多，但是要注意一下，实现后面的for循环i是等于n的，因为不能从第一个数字进行这个运算，所以掌握这种思维的灵活运用还是挺重要的，如果再次遇到这种会超时的题目不妨试试换个思路
3. 当然还可以用在循环里输入的时候直接完成了相乘和相加的工作，还是要多练题，想法有了但是一直写不出来，或者各种小问题；