指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:11617

签 名:

数学改变科学,科学改变世界

等  级
排  名 17
经  验 18172
参赛次数 45
文章发表 98
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:

我们观察式子可以发现,可以把每一个数提出来,以a1到a5为例

S=a1*(a2+a3+a4+a5)+a2*(a3+a4+a5)+a3*(a4+a5)+a4*a5

这样很容易想到前缀和,我们可以通过前缀和来得到括号里面的数,这样时间复杂度就降到了O(n)

参考代码:

#include <stdio.h>

long long  p[200007];
long long dp[200007];//开到long long 来存放这些数之和

int main (){
	int i,j;
	int n;
	long long z=0;//注意开到long long
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
		if(i==0)dp[i]=p[i];
		else 	dp[i]=dp[i-1]+p[i];//前缀和数组
	}
	for(i=0;i<n;i++){
		z+=p[i]*(dp[n-1]-dp[i]);//dp[n-1]-dp[i]即为()里的数
	} 
	printf("%lld",z);
	
	return 0;
}

还有另一种算法,时间复杂度是O(n)但是不需要开辟数组。

代码如下:

#include <stdio.h>

int main ()
{
	int i;
	int n,m;
	long long k=0,z=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&m);
		z+=k*m;
		k+=m;
	}
	printf("%lld",z);
	
	return 0;
}

这样的做法就是把式子拆成:

S=a2*a1+a3*(a2+a1)+a4*(a3+a2+a1)+a5*(a4+a3+a2+a1)

通过调整式子结构,就可以一边求前缀和一边相加了。

 

0.0分

28 人评分

  评论区