蓝桥杯真题 求和 给定 n 个整数 a1· a2, · · · , an，求它们两两相乘再相加的和

求和

问题描述

给定 n 个整数 a₁, a₂, · · · , a_n ，求它们两两相乘再相加的和，即：
S=a₁·a₂+a₁·a₃+···+a₁·a_n+a₂·a₃+···+a_n-2·a_n+a_n-1·a_n

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数a₁, a₂, · · · , a_n

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

样例输入

4
1 3 6 9

样例输出

117

评测用例规模与约定

对于 30% 的数据，1≤n≤1000,1≤a_i ≤100 。

对于所有评测用例， 1≤n≤200000,1≤a_i≤1000 。

运行限制

·最大运行时间：1s
·最大运行内存: 512M

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long n,temp,x,sum;
	cin >> n;
	x=0;
  	sum=0;
	for (long long i = 0; i < n; i++) {
		scanf("%d", &temp);
		sum += x * temp;
		x += temp;
	}
	cout << sum;
	return 0;
}

思路

看到题目的第一个思路就是全部读取到一个数组里面，然后双重循环来计算，此时的时间复杂度为O(n²)，当数据量很大的时候还是比较慢的。观察计算式，提取公因式可以发现原计算式可以化为
S=a₁·a₂+(a₁+a₂)·a₃+(a₁+a₂+a₃)·a₄+···+(a₁+a₂+a₃+···+a_n-2+a_n-1)·a_n
所以我们只要维护一个当前读取进来的不包括当前数字的前缀和然后每次与当前的数字相乘然后累加即可，就可以得到上面的代码，这种方法只需要循环一边即可时间复杂度为O(n)。