博客

问题描述

给定 n 个整数 1,2,⋅⋅⋅,a1​,a2​,⋅⋅⋅,an​ ，求它们两两相乘再相加的和，即：

S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

输入格式

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

第二行包含 n 个整数 1,2,⋯,a1​,a2​,⋯,an​。

输出格式

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

样例输入

4
1 3 6 9

样例输出

117

评测用例规模与约定

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

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

运行限制

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

代码：

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  // 请在此输入您的代码
  long n,sum=0,i,j=0;
  int a[200000];
  scanf("%ld",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  for(i=1;i<n;i++){ //从a[1]*a[0]加到a[n-1]*(a[n-2]+...+a[0])
    j+=a[i-1];
    sum+=a[i]*j;
  }
  printf("%ld",sum);
  return 0;
}

思路：

参考官网刷题的C语言题解第一个，直接暴力用两个for循环会运行超时，所以把求和公式转换一下，变成从a[1]*a[0]加到a[n-1]*(a[n-2]+…+a[0])，只需要一层循环就行