给定 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,表示所求的和。请使用合适的数据类型进行运算。
4
1 3 6 9
117
对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ ai ≤ 100。
对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000。
题目解析
这道题,给我的第一印象是用前缀和。
如何处理相乘关系?
便输入边计算?时间复杂度在O(n^3),优化一下可以到n^2
下面是代码。
#include <iostream>
#include "algorithm"
#include "string.h"
using namespace std;
int main(){
int n;
cin>>n;
int a[n+1],b[n+1][n+1],c[n+1][n+1];
memset(a,0,sizeof a);
memset(b,1,sizeof b);
memset(c,0,sizeof c);
for (int i = 1; i <= n; ++i) {
cin>>a[i];
}
for (int i = 1; i <= n; ++i) {
for(int j=i;j<=n;++j){
b[i][j]=a[i]*a[j];//b[i][j]表示a[i]*a[j]的积
c[i][j]=c[i][j-1]+b[i][j];//前缀和
if(j==i)c[i][j]=c[i-1][n];//当a[i]开始变换时,存储值转移
}
}
cout<<c[n][n];
}
当然,这样子做空间复杂度太大了,我们还可以优化空间复杂度,没错,就是用滚动数组。
#include <iostream>
#include "string.h"
using namespace std;
int a[200005],b[2][200005],c[2][200005];
int main(){
int n;
cin>>n;
memset(a,0,sizeof a);
memset(b,1,sizeof b);
memset(c,0,sizeof c);
for (int i = 1; i <= n; ++i) {
cin>>a[i];
}
for (int i = 1; i <= n; ++i) {
for(int j=i;j<=n;++j){
b[i&1][j]=a[i]*a[j];
c[i&1][j]=c[i&1][j-1]+b[i&1][j];
if(j==i)c[i&1][j]=c[(i-1)&1][n];
}
}
cout<<c[n&1][n];
}
当然,时间复杂度还是有点大。
我们不难发现,我们每次可以提一个a[i]出来,那么每次计算的都是一个子前缀和,那么这样的话就很好办了,看代码
#include <iostream>
using namespace std;
long long a[200005];
long long b[200005];
int main(){
int n;
cin>>n;
for (int i = 1; i <= n; ++i) {
cin>>b[i];
a[i]=a[i-1]+b[i];
}
long long sum=0;
for(int i=1;i<=n;i++){
sum+=b[i]*(a[n]-a[i]);
}
cout<<sum;
}
正文完