给定 n 个整数 a1,a2,⋅⋅⋅,an，求它们两两相乘再相加的和，即
S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+an−1⋅an
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋅⋅⋅,an。
输出格式
输出一个整数 S，表示所求的和。
请使用合适的数据类型进行运算。
数据范围
对于 30% 的数据，1≤n≤1000，1≤ai≤100。
对于所有评测用例，1≤n≤200000，1≤ai≤1000。
输入样例：
4 1 3 6 9
输出样例：
117
我的思路：
- 对于所有的样例，把所有的数相乘再相加一共需要O(n2)的时间复杂度，计算次数达到1010，所以需要优化到O(nlog2n)甚至是O(n)
- 而且对于1010的空间也是超出题目要求的存储范围的
- 对于一个已经输入完成的序列 a1,a2,⋅⋅⋅,an，从前向后遍历
当遍历到某个数ai时，只需要将这个数与前面的所有的数分别相乘再相加
- 这就等价于这个数 ai与前面的所有数的和相乘（前缀和）
我的代码：
#include<iostream> using namespace std; typedef long long LL; //根据a[i]的范围，可能会爆int const int N = 2e5+10; int a[N], n; LL b[N], c[N], res = 0; //大块空间定义在全局区，不然会爆栈 int main(){ cin >> n; for(int i = 0; i < n; i++){ //输入的同时进行计算 cin >> a[i]; if(i == 0) b[i] = 0; //b[i]保存的是a的前面的数的前缀和 else{ b[i] = a[i-1]+b[i-1]; //更新前缀和 c[i] = a[i]*b[i]; //根据前缀和计算当前位置的数与前面的所有数的和的乘积 } } for(int i = 1; i <= n; i++) res += c[i]; cout << res; return 0; }
利用前缀和，直接将时间和空间复杂度从O(n2)优化到O(n)
前面失败的尝试：
- 利用空间换时间，但是对于1010的数组空间无法分配（Segmentation Fault）
#include<iostream> using namespace std; const int N = 2e5+10; int n, k = 2, res = 0, a[N]; int main(){ cin >> n; int b[n*(n-1)/2+1]; for(int i = 1; i <= n; i++){ cin >> a[i]; for(int j = 1; j < i; j++){ b[k++] = a[j]*a[i]; } } b[1] = a[1]; for(int i = 2; i <= n*(n-1)/2+1; i++){ res += b[i]; } cout << res << endl; return 0; }
- 换成vector，虽然定义在全局区不会出现爆栈，但是超出了要求的256MB空间大小（Memory Limit Exceeded）
#include<iostream> #include<vector> using namespace std; typedef long long LL; const int N = 2e5+10; int n, k = 2, a[N]; vector<LL> v; int main(){ cin >> n; LL res = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; for(int j = 1; j < i; j++){ v.push_back(a[j]*a[i]); } } for(int i = 0; i <= n*(n-1)/2-1; i++){ res += v[i]; } cout << res << endl; return 0; }
